Đế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ó 4 trả lời

#1 Explorer

Explorer

    Binh nhất

  • Thành viên mới
  • 42 Bài viết

Đã gửi 22-06-2022 - 16:36

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

 


#2 Hoang72

Hoang72

    Sĩ quan

  • Thành viên
  • 367 Bài viết
  • Giới tính:Nam
  • Đến từ:Hà Tĩnh
  • Sở thích:(^_^)

Đã gửi 23-06-2022 - 14:29

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

    Binh nhất

  • Thành viên mới
  • 42 Bài viết

Đã gửi 26-06-2022 - 09:18

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

    Sĩ quan

  • Thành viên
  • 367 Bài viết
  • Giới tính:Nam
  • Đến từ:Hà Tĩnh
  • Sở thích:(^_^)

Đã gửi 26-06-2022 - 19:12

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

  • Điều hành viên Đại học
  • 643 Bài viết
  • Giới tính:Nam
  • Đến từ:Khoa Toán, Trường Đại học Khoa học Tự nhiên, ĐHQGHN

Đã gửi 27-06-2022 - 09:17

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


$\sum_{P} I(P, F\cap G)=mn$

 

"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






Đượ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