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'$.
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 Trung học Cơ sở →
Số học →
$x^2+y^2+1\vdots 2xy+1$Bắt đầu bởi Pi1576, 13-05-2024 số học |
|
|||
Toán Trung học Cơ sở →
Số học →
$a! + b! + c! = 2^{d}$Bắt đầu bởi Khanh369, 10-05-2024 giai thừa, số học |
|
|||
Solved
Toán Trung học Cơ sở →
Số học →
$2^{a!} + 2^{b!} = c!$Bắt đầu bởi Khanh369, 08-05-2024 giai thừa, số học |
|
|||
Toán thi Học sinh giỏi và Olympic →
Tổ hợp và rời rạc →
Có bao nhiêu cách viết số nguyên dương n thành tổng các số nguyên dương?Bắt đầu bởi Explorer, 24-04-2024 tổ hợp, đếm, nguyên dương và . |
|
|||
|
Toán Trung học Cơ sở →
Số học →
Chứng minh rằng $(a_{1}^{2}+1)(a_{2}^{2}+1)...(a_{2024}^{2}+1)$ không chia hết cho $(a_{1}.a_{2}...a_{2024})^2$Bắt đầu bởi Nguyentrongkhoi, 26-03-2024 số học |
|
0 thành viên, 1 khách, 0 thành viên ẩn danh