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@@
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.
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
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
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
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.
Toán thi Học sinh giỏi và Olympic →
Số học →
Chứng minh rằng $x^2 + y^2 + z^2 - 2(xy + yz + zx)$ là số chính phươngBắt đầu bởi Chuongn1312, 13-03-2024 toán olympic, số học |
|
|||
Toán thi Học sinh giỏi và Olympic →
Số học →
$\sum_{n\vdots d,d=2k+1}\varphi (d)2^{\frac{n}{d}} \hspace{0.2cm} \vdots \hspace{0.2cm} n$Bắt đầu bởi hovutenha, 08-03-2024 tổ hợp, số học |
|
|||
Solved
Toán Trung học Cơ sở →
Đại số →
$f(a)-f(b) \vdots a-b$Bắt đầu bởi Sa is very stupid and lazy, 17-01-2024 số học |
|
|||
Toán thi Học sinh giỏi và Olympic →
Số học →
$x^n+n \vdots p^m$Bắt đầu bởi trinhgiahuy2008, 15-01-2024 số học |
|
|||
Toán Trung học Cơ sở →
Số học →
Với hai số tự nhiên a,b bất kì thỏa mãn (a,b)=1, hãy chứng minh rằng: $(2^a-1,2^b-1)=1$Bắt đầu bởi Nguyenthu2504, 14-11-2023 số học |
|
0 thành viên, 1 khách, 0 thành viên ẩn danh