Chủ đề này có 6 trả lời

[uyenha]

giả sử m,n là các số nguyên dương sao cho $\varphi (5^{m}-1)=5^{n}-1$.cmr UCLN của m và n lớn hơn 1

[Stranger411]

giả sử m,n là các số nguyên dương sao cho $\varphi (5^{m}-1)=5^{n}-1$.cmr UCLN của m và n lớn hơn 1

Very beautiful !! A problem in quadratic residue

Bổ đề: Cho các số nguyên $m,n$ và $a>1$. Ta có: $\gcd \left( {{a^m} - 1,{a^n} - 1} \right) = {a^{\gcd \left( {m,n} \right)}} - 1$

Lời giải bài toán:
Giả sử $gcd(m,n)=1$
Ta xét phân tích cơ sở: ${5^m} - 1 = {2^a}{p_1}^{{a_1}} \ldots {p_k}^{{a_k}}$ với ${p_i} > 2$
Vậy nên:
\[{5^n} - 1 = \varphi \left( {{5^m} - 1} \right) = {2^{a - 1}}{p_1}^{{a_1} - 1}...{p_k}^{{a_k} - 1}\prod\limits_{i = 1}^k {\left( {{p_i} - 1} \right)} \]
Vì ${2^a}|{5^n} - 1$. Kết hợp với bổ đề, ta có: $\gcd \left( {{5^m} - {{1,5}^n} - 1} \right) = 5 - 1 = 4$
Vậy nên $a=2$
Vì ${2^3}|{5^m} - 1 \Rightarrow m = 2k + 1 \Rightarrow {p_i}|5.{\left( {{5^k}} \right)^2} - 1$
Vậy 5 là số chính phương (mod $p_i$) nên ${p_i} \equiv - 1(\bmod 5)$
$$ \Rightarrow \left\{ \begin{gathered}
{\left( { - 1} \right)^k} = 1 \\
{\left( { - 2} \right)^{k + 1}} \equiv 1(\bmod 5) \\
\end{gathered} \right.
\Rightarrow \left\{ \begin{gathered}
k \equiv 0(\bmod 2) \\
k \equiv 3(\bmod 4) \\
\end{gathered} \right.$$
Mâu thuẫn,
Vậy $gcd(m,n)>1$.

Bài viết đã được chỉnh sửa nội dung bởi Stranger411: 11-08-2012 - 13:44

[nguyenta98]

\[{5^n} - 1 = \varphi \left( {{5^m} - 1} \right) = {2^{a - 1}}{p_1}^{{a_1} - 1}...{p_k}^{{a_k} - 1}\prod\limits_{i = 1}^k {\left( {{p_i} - 1} \right)} \]

He he, thú thực vs anh là em làm y như anh đó, nhưng cả bài của anh và em đều thiếu một cái quan trọng đó là mũ của $p_i$ có thể bằng $0$ anh hiểu ko (hay $a_i-1=0$ đó) nên chưa làm gì được ở đoạn số chính phương $mod(p)$ đâu cho nên bài này vẫn cần phải nghĩ thêm

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 11-08-2012 - 14:09

[Stranger411]

He he, thú thực vs anh là em làm y như anh đó, nhưng cả bài của anh và em đều thiếu một cái quan trọng đó là mũ của $p_i$ có thể bằng $0$ anh hiểu ko (hay $a_i-1=0$ đó) nên chưa làm gì được ở đoạn số chính phương $mod(p)$ đâu cho nên bài này vẫn cần phải nghĩ thêm

Very beautiful !! A problem in quadratic residue

Bổ đề: Cho các số nguyên $m,n$ và $a>1$. Ta có: $\gcd \left( {{a^m} - 1,{a^n} - 1} \right) = {a^{\gcd \left( {m,n} \right)}} - 1$

Lời giải bài toán:
Vì ${2^3}|{5^m} - 1 \Rightarrow m = 2k + 1 \Rightarrow {p_i}|5.{\left( {{5^k}} \right)^2} - 1$
Vậy 5 là số chính phương (mod $p_i$) nên ${p_i} \equiv - 1(\bmod 5)$
$$ \Rightarrow \left\{ \begin{gathered}
{\left( { - 1} \right)^k} = 1 \\
{\left( { - 2} \right)^{k + 1}} \equiv 1(\bmod 5) \\
\end{gathered} \right.
\Rightarrow \left\{ \begin{gathered}
k \equiv 0(\bmod 2) \\
k \equiv 3(\bmod 4) \\
\end{gathered} \right.$$
Mâu thuẫn,
Vậy $gcd(m,n)>1$.

Thực ra ko phải nghĩ gì cho nhiều em à
Từ đoạn này trở xuống mình xét ${5^m} - 1$ nên chả có liên quan gì đến $a_i -1=0$ cả :-j
Với lại $a_i -1=0$ ko quan trọng khi chứng minh $a=2$ ở phần trên

Và từ đẳng thức:
\[{5^n} - 1 = \varphi \left( {{5^m} - 1} \right) = {2^{a - 1}}{p_1}^{{a_1} - 1}...{p_k}^{{a_k} - 1}\prod\limits_{i = 1}^k {\left( {{p_i} - 1} \right)} \]
cho ta ${p_i} \not \equiv 1(\bmod 5)$ cũng chẳng liên quan gì đến $a_i -1=0$ em à

Bài viết đã được chỉnh sửa nội dung bởi Stranger411: 11-08-2012 - 14:20

[nguyenta98]

Thực ra ko phải nghĩ gì cho nhiều em à
Từ đoạn này trở xuống mình xét ${5^m} - 1$ nên chả có liên quan gì đến $a_i -1=0$ cả :-j
Với lại $a_i -1=0$ ko quan trọng khi chứng minh $a=2$ ở phần trên

Và từ đẳng thức:
\[{5^n} - 1 = \varphi \left( {{5^m} - 1} \right) = {2^{a - 1}}{p_1}^{{a_1} - 1}...{p_k}^{{a_k} - 1}\prod\limits_{i = 1}^k {\left( {{p_i} - 1} \right)} \]
cho ta ${p_i} \not \equiv 1(\bmod 5)$ cũng chẳng liên quan gì đến $a_i -1=0$ em à

Ặc, ý em nó là nếu $a_i-1=0$ thì cái $p_i^{a_i-1}=p_i^0=1$ nên có tồn tại $p_i$ nữa đâu mà số chính phương $mod(p)$ nữa?

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 11-08-2012 - 14:37

[Stranger411]

Ặc, ý em nó là nếu $a_i-1=0$ thì cái $p_i$ có tồn tại đâu mà số chính phương $mod(p)$ nữa?

Ko ko, em nhầm hàng rồi :|
mình ko xét cái $\varphi (5^{m}-1)$ đâu
chỉ cần xét ${5^m} - 1 = {2^a}{p_1}^{{a_1}} \ldots {p_k}^{{a_k}}$.
Từ cái này ta chứng minh 5 là số chính phương $mod(p)$ là ok rồi

[anh qua]

Đài Loan 2005