5 replies to this topic

[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ữa@@

 

[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ữa@@

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'$.

[Hoang72]

Bài này làm mình liên tưởng đến cấp của số nguyên và ai ngờ nó giống thật. Không biết cái này thì người ta gọi là gì nhỉ:

Gọi $h$ là số nguyên dương nhỏ nhất sao cho $m\mid a^h - b^h$.

Khi đó nếu $x$ là số nguyên dương thoả mãn $m\mid a^x - b^x$ thì $h\mid x$.

Thật vậy, giả sử $x = hq + r$ với $0 < r < h$ thì $(a^h)^q . a^r \equiv (b^h)^q . b^r\pmod m\Rightarrow a^r\equiv b^r\pmod m$, vô lí theo cách chọn $h$.

Và nếu $h\mid x$ thì ta cũng dễ dàng có được $m\mid a^x-b^x$.

Áp dụng vào bài toán này thì ta có đpcm.