Chủ đề này có 4 trả lời

[Explorer]

Cho a,b,m là các số nguyên dương thỏa mãn:

(a,m)=(b,m)=1

$a^{x}\equiv b^{x}$ (mod m)

$a^{y}\equiv b^{y}$ (mod m)

CMR $a^{gcd(x,y)}\equiv b^{gcd(x,y)}$ (mod m)

cái tính chất này mik ko bt có đúng hay ko nữ[email protected]@

 

[Hoang72]

Mình nghĩ là như thế này, không biết chuẩn không.

Ta chỉ cần xét trường hợp $x\neq y$.

Giả sử $x>y$.

Đặt $x=yq+r(r,q\in\mathbb N^*; r<y)$.

Nếu $r=0$ thì $\gcd(x,y) = y$ nên bài toán hiển nhiên đúng.

Nếu $r>0$ thì $(a^y)^q.a^r\equiv (b^y)^q.b^r\pmod m$.

Do $(a,m)=(b,m)=1$ và $a^y\equiv b^y\pmod m$ nên $a^r\equiv b^r\pmod m$.

Lúc này, $\gcd(x,y)=\gcd(y,r)$ nên lặp lại liên tục, ta có bài toán đúng theo giải thuật Euclid.

 

 

[Explorer]

Mình nghĩ là như thế này, không biết chuẩn không.

Ta chỉ cần xét trường hợp $x\neq y$.

Giả sử $x>y$.

Đặt $x=yq+r(r,q\in\mathbb N^*; r<y)$.

Nếu $r=0$ thì $\gcd(x,y) = y$ nên bài toán hiển nhiên đúng.

Nếu $r>0$ thì $(a^y)^q.a^r\equiv (b^y)^q.b^r\pmod m$.

Do $(a,m)=(b,m)=1$ và $a^y\equiv b^y\pmod m$ nên $a^r\equiv b^r\pmod m$.

Lúc này, $\gcd(x,y)=\gcd(y,r)$ nên lặp lại liên tục, ta có bài toán đúng theo giải thuật Euclid.

mik ko hiểu cái đoạn triệt tiêu thành a^r đồng dư b^r mod m lắm

[Hoang72]

mik ko hiểu cái đoạn triệt tiêu thành a^r đồng dư b^r mod m lắm

Do $a^y\equiv b^y\pmod m$ nên $(a^y)^q\equiv (b^y)^q\pmod m$.

Mà hai số này đều nguyên tố cùng nhau với $m$ nên có thể rút gọn được.

P/s: Mong không có lỗi gì ở đây

[vutuanhien]

mik ko hiểu cái đoạn triệt tiêu thành a^r đồng dư b^r mod m lắm

Nếu $ac\equiv bc$ mod $m$ và $(c, m)=1$ thì $a\equiv b$ mod $m$.

 

Cho a,b,m là các số nguyên dương thỏa mãn:

(a,m)=(b,m)=1

$a^{x}\equiv b^{x}$ (mod m)

$a^{y}\equiv b^{y}$ (mod m)

CMR $a^{gcd(x,y)}\equiv b^{gcd(x,y)}$ (mod m)

cái tính chất này mik ko bt có đúng hay ko nữ[email protected]@

Bạn có thể sử dụng công thức Bezout: Với $x, y$ là các số nguyên thì tồn tại $x', y'\in \mathbb{Z}$ sao cho $gcd(x, y)=xx'+yy'$.