Here is a solution. Let $5^m-1={p_1}^{\alpha_1}{p_2}^{\alpha_2}...{p_k}^{\alpha_k}$ where $p_i$'s are distinct prime numbers and $\alpha_i$'s are natural numbers. Then $5^n-1={p_1}^{\alpha_1-1}{p_2}^{\alpha_2-1}...{p_k}^{\alpha_k-1}(p_1-1)(p_2-1)...(p_k-1)$ Suppose that $\gcd (m,n)=1.$ We will get a contradiction. If $\gcd (m,n)=1,$ then $\gcd (5^m-1, 5^n-1)=5^{\gcd(m,n)}-1 = 4$ So, $p_1=2, \alpha_1=2, \alpha_i=1$ for all $i=2,3,...,k$ Note that if $\alpha_1=3,$ then $k$ must be $1$ and therefore $n=1, \: 5^m-1=8$ which is impossible. Renumbering the primes, we get $5^m-1=4q_1q_2...q_r$ and $5^n-1=2(q_1-1)(q_2-1)...(q_r-1)$ Now, $m$ must be an odd number, because otherwise $8 \mid 5^m-1$ So, $5^m \equiv 1 \pmod {q_i}$ for all $i=1,2,...,r$ Since $m$ is odd, $5^{m+1} \equiv 5 \pmod {q_i}$ and hence $\left(\frac{5}{q_i}\right)=1$ where $\left(\frac{a}{b}\right)$ denotes the Legendre symbol. By Quadratic Residue theorem; $\left(\frac{5}{q_i}\right) \cdot \left(\frac{q_i}{5}\right) = (-1)^{\frac{5-1}{2}\cdot \frac{q_i-1}{2}}=1$ So, we get $\left(\frac{q_i}{5}\right) =1$ Therefore, $q_i \equiv 4 \pmod 5$ since the square residues modulo $5$ are $1$ and $4$ and $q_i \not\equiv 1 \pmod 5$ since $5 \nmid 5^n-1$ So, $5^m-1 \equiv 4^{r+1} \pmod 5$ and $5^n-1 \equiv 2 \cdot 3^r \pmod 5$ From the first one we get $r$ must be even. Take $r=2u$ and substitute it in the second equivalence. $-1 \equiv 2 \cdot 9^u \pmod 5$ and therefore $(-1)^u \equiv 2 \pmod 5$ which is impossible. So, we are done. Remark: I think that this is one of the Korean National Olympiad problems. Edit: It was Taiwan, .

It is a problem from AMM.See Pen with title:Divisor Funtions

I need an elementary solution...not using the Quadratic Residue theorem Thx

1)It's called "Quadratic reciprocity law", not "Quadratic Residue theorem" 2)The quadratic reciprocity law is part of elementary number theory i.e it can be proved(though not necessarily easily) wihout any tools from algebraic or analytic number theory.

crazyfehmy wrote: By Quadratic Residue theorem; $\left(\frac{5}{q_i}\right) \cdot \left(\frac{q_i}{5}\right) = (-1)^{\frac{5-1}{2}\cdot \frac{q_i-1}{2}}=1$ I said that because he/she said ! I know that it's elementary,but i want a solution without using it !

He is he I mean male. (I killed English:( ) But i cant understand this opinion(Atlas's opinion). Can we say "i dont want to use numbers in my proof.Can someone give me a proof without numbers." Certainly no. Secondly its very elemantary and its easy to verify same things with using different methods. So its not logical to discuss that. You have to just try to learn legendre symbol.

Just to link the two threads: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=354902

my solution: Assume for a sake of a contradiction that $(m,n)=1,5^n-1=\phi (5^m-1)$ let $5^m-1=2^ap_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ where $p_1,p_2,\cdots ,p_k$ are primes from the condition $5^n-1=\phi (5^m-1)=2^{a-1}p_1^{a_1-1}p_2^{a_2-1}\cdots p_k^{a_k-1}(p_1-1)(p_2-1)\cdots (p_k-1)$(2) note that because $\text{gcd} (5^n-1,5^m-1)=5^{(m,n)}-1=5^1-1=4,2^a\mid 5^n-1$ we have $a=2,a_i=1$ for $1\le i\le k$ note that $m$ is odd number because otherwise $8\mid 5^m-1,8\mid 5^n-1\longrightarrow 8\mid (5^n-1,5^m-1)=4$ which is absurd .so $m=2t+1$ for some integer $t$ .because $p_i\mid 5.(5^t)^2-1\longrightarrow 5\equiv ((5^t)^{-1})^2\pmod{p_i}$ ($(5^t)^{-1}$ is inverse of $5^t$ modulo $p_i$) so $5$ is quadratic reside modulo $p_i$ so $(\frac{5}{p_i})=1$(1) now from quadratic reside law $(\frac{5}{p_i})({p_i}{5})=(-1)^{2(p_i-1)}=1$ using (1) we deduce that $(\frac{p_i}{5})=1\longrightarrow p_i\equiv 1,-1\pmod{5}$ so $p_i$ is either in a form $5l+1$ or $5l-1$. From (2) we deduce that none of $p_i-1$ is divisible by $5$(because the LHS of (2) isn't divisible by $5$) so for every $1\le i\le k$ we have $p_i\equiv -1\pmod{5}$ but note that $5^{m}-1=4p_1p_2\cdots p_k \longrightarrow -1\equiv (-1)^{k+1}$ so $k$ is even(3) but from (2),(3) $5^n-1=2(p_1-1)(p_2-1)\cdots (p_k-1)\longrightarrow -1\equiv 2\times (-2)^k\equiv 2^{k+1}\pmod{5}\longrightarrow 5\mid 2^{k+1}+1\longrightarrow 2^{2(k+1)}\equiv 1\pmod{5}$ but since $4$ is order of $2$ modulo $5$ we must have $4\mid 2(k+1)\longrightarrow 2\mid k+1$ which is a contradiction because $k$ is even. DONE

WakeUp wrote: Suppose that for some $m,n\in\mathbb{N}$ we have $\varphi (5^m-1)=5^n-1$, where $\varphi$ denotes the Euler function. Show that $(m,n)>1$. Pretty straightforward. Assume otherwise, that $(m,n) = 1$. Define $o(n)$ as the largest odd factor of $n$. Claim 01. $o(5^m - 1)$ is squarefree. Proof. We have \[ \gcd(5^m - 1, \gcd(5^m - 1)) = \gcd( 5^m - 1, 5^n - 1) = 5^{\gcd(m,n)} - 1 = 4\]Now, suppose there exists an odd prime $p$ such that $p^2 \mid 5^m - 1$, then $p \mid \varphi(5^m - 1) = 5^n - 1$, and as a result, $p \mid \gcd(5^m - 1, \varphi(5^m - 1)) = 4$, which is a contradiction. Therefore, we can write: \begin{align*} 5^m - 1 &= 2^{\alpha} p_1 p_2 \dots p_k \\ 5^n - 1 &= 2^{\alpha - 1} (p_1 - 1)(p_2 - 1) \dots (p_k - 1) \end{align*}where $p_1, p_2, \dots, p_k$ are odd prime factors of $5^m - 1$. Note that this must exists, or otherwise \[ 5^m - 1 = 2^{\alpha} = 2(2^{\alpha - 1}) = 2(5^n - 1) \le 2(5^{m - 1} - 1) < 5^m - 1 \]which is a contradiction. Therefore, $\alpha = \min \{ \nu_2(5^m - 1), \nu_2(5^n - 1) \} = 2$ by definition of gcd. Hence, we have \begin{align*} 5^m - 1 &= 4p_1 p_2 \dots p_k \\ 5^n - 1 &= 2(p_1 - 1)(p_2 - 1) \dots (p_k - 1) \end{align*}Claim 02. $m$ is odd. Proof. Suppose otherwise, then $4 \equiv 5^m - 1 \equiv 0 \ (\text{mod} \ 8)$, which is a contradiction. Claim 03. $p_i \equiv 4 \ (\text{mod} \ 5)$ for every $1 \le i \le k$. Now, notice that for every $p_i$, we have \[ 5^{m + 1} \equiv 5 \ (\text{mod} \ p_i) \]Therefore, $\left( \frac{5}{p_i} \right) = 1$ for every $p_i$. By Quadratic Reciprocity Law, we have $\left( \frac{5}{p_i} \right) = \left( \frac{p_i}{5} \right)$. Thus, we conclude that $p_i \equiv 1, 4 \ (\text{mod} \ 5)$. Suppose there exists $j$ such that $p_j \equiv 1 \ (\text{mod} \ 5)$, then \[ 5 \mid p_j - 1 \mid 5^n - 1 \]which is a contradiction. To finish this, notice that \[ 4 \equiv 5^m - 1 \equiv 4p_1 p_2 \dots p_k \equiv 4^{k + 1} \ (\text{mod} \ 5) \]which forces $k$ to be even. However, \[ 4 \equiv 5^n - 1 \equiv 2(p_1 - 1)(p_2 - 1) \dots (p_k - 1) \equiv 2 \cdot 3^k \equiv 2 \cdot (-1)^{\frac{k}{2}} \ (\text{mod} \ 5) \]which is a big contradiction as $RHS \equiv 2, 3 \ (\text{mod} \ 5)$. Hence, our original conclusion is wrong, and we must have $(m,n) > 1$.

For the sake of contradiction assume not,then $\gcd(5^m-1,5^n-1)=5^{\gcd(m,n)}-1=4$ Claim: $\phi(5^m+1)$ is square free. Proof: Now, suppose there exists an odd prime $p$ such that $p^2 \mid 5^m - 1$, then $p \mid \varphi(5^m - 1) = 5^n - 1$, and as a result, $p \mid \gcd(5^m - 1, \varphi(5^m - 1)) = 4$, which is a contradiction. Hence, we can write: \begin{align*} 5^m - 1 &= 2^{\alpha} p_1 p_2 \dots p_k \\ 5^n - 1 &= 2^{\alpha - 1} (p_1 - 1)(p_2 - 1) \dots (p_k - 1) \end{align*}Claim: $\alpha=2$ Proof: Since $\gcd(5^m-1,5^n-1)=5^{\gcd(m,n)}-1=4$ so $\alpha=2$ Hence, we have \begin{align*} 5^m - 1 &= 4p_1 p_2 \dots p_k \\ 5^n - 1 &= 2(p_1 - 1)(p_2 - 1) \dots (p_k - 1) \end{align*}If $n$ was even then $5^n-1 \equiv (-3)^n-1 \equiv (-1)^n-1 \equiv 0 \pmod 4$,a contradiction so $n$ must be even. Now,Claim: $p_i \equiv -1 \pmod 5$ Proof: Since $5^n \equiv 1 \pmod {p_i}$ by the quadratic reciprocity law $p_i$ is a quadratic residue $\pmod 5$ so $p_i \equiv \pm 1 \pmod 5$ Now $p_i \equiv 1 \pmod 5$,implies $5^n-1 \equiv 1 \pmod 5$,a contradiction. By this, \[ 4 \equiv 5^m - 1 \equiv 4p_1 p_2 \dots p_k \equiv 4^{k + 1} \ (\text{mod} \ 5) \]which forces $k$ to be even. However, \[ 4 \equiv 5^n - 1 \equiv 2(p_1 - 1)(p_2 - 1) \dots (p_k - 1) \equiv 2 \cdot 3^k \equiv 2 \cdot (-1)^{\frac{k}{2}} \ (\text{mod} \ 5) \]a contradiction so we are done.$\blacksquare$