Đến nội dung

Hình ảnh

Cho a,b,m ngdg TM: (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)

- - - - - số học số đồng dư mod nguyên dương nguyên gcd ước chung lớn nhất ước chung ước

  • Please log in to reply
Chủ đề này có 5 trả lời

#1
Explorer

Explorer

    Trung sĩ

  • Thành viên
  • 155 Bài viết

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@@

 


#2
Hoang72

Hoang72

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 539 Bài viết

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.

 

 



#3
Explorer

Explorer

    Trung sĩ

  • Thành viên
  • 155 Bài viết

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



#4
Hoang72

Hoang72

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 539 Bài viết

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



#5
vutuanhien

vutuanhien

    Thiếu úy

  • ĐHV Toán Cao cấp
  • 688 Bài viết

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


"The first analogy that came to my mind is of immersing the nut in some softening liquid, and why not simply water? From time to time you rub so the liquid penetrates better, and otherwise you let time pass. The shell becomes more flexible through weeks and months—when the time is ripe, hand pressure is enough, the shell opens like a perfectly ripened avocado!" - Grothendieck


#6
Hoang72

Hoang72

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 539 Bài viết

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.







Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: số học, số, đồng dư, mod, nguyên dương, nguyên, gcd, ước chung lớn nhất, ước chung, ước

1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh