Let $p\le q$, then $p\ge 3$ and $p=3\to q=3$. If $p\ge 5$ consider prime divisor $q\ge p$ of number $\Phi_{p-1}(2)$, then $q|2^{p-1}-1$, and $p-1|q-1\to p|2^{q-1}-1$. For $p=5$ we found $q|\Phi_4(2)=5$. But for $p>5$ we always found $q>p$.

Rust wrote: Let $p\le q$, then $p\ge 3$ and $p=3\to q=3$. If $p\ge 5$ consider prime divisor $q\ge p$ of number $\Phi_{p-1}(2)$, then $q|2^{p-1}-1$, and $p-1|q-1\to p|2^{q-1}-1$. For $p=5$ we found $q|\Phi_4(2)=5$. But for $p>5$ we always found $q>p$. What do you mean by $\Phi_{p-1}(2)$? This is my solution: First we need a lemma: Lemma. Let $a,b$ are two co-prime positive integers and $k\in \mathbb{N}$. Prove that if $p$ is an odd prime number such that \[p\mid{a^{{2^k}}} + {b^{{2^k}}}\] then $p\equiv 1(\bmod 2^{k+1})$. Proof. We have: \[{a^{{2^k}}} \equiv - {b^{{2^k}}}(\bmod p) \Rightarrow {(xb)^{{2^k}}} \equiv - 1(\bmod p)\] with $x$ is the inverse of $a$ modulo $p$. Then ${(xb)^{{2^{k + 1}}}} \equiv 1(\bmod p)$. Denote $ord_pxb=q$, then $q\mid 2^{k+1}$ and thus $q=2^s,s\le k+1$. If $s<k+1$, then $s\le k$, thus $(xb)^q\equiv (xb)^{2^s}\equiv 1(\bmod p)$, or $p\mid (xb)^{2^s}-1\mid (xb)^{2^k}-1$, but $p\mid (xb)^{2^k}+1$, which a contradiction. Hence $s=k+1$, so $p\equiv 1 (\bmod 2^{k+1})$. Our lemma is proved. $\square$ Come back to our problem: Denote $F_n$ be the Fermat number $2^{2^n}+1$, and denote $p$ is the odd prime divisor of $F_n$. According to the lemma, we have $p\equiv 1 (\bmod 2^{n+1})$ and $ord_p2=2^{n+1}$. Thus $2^{n+1}\mid p-1$ so $p$ is the prime number of the form $8k+1$, and so $2$ is the quadratic residue modulo $p$, thus \[{2^{\frac{{p - 1}}{2}}} - 1 \equiv 0(\bmod p) \Rightarrow or{d_p}2\mid\frac{{p - 1}}{2} \Rightarrow {2^{n + 1}}\mid\frac{{p - 1}}{2} \Rightarrow p \equiv 1(\bmod {2^{n + 2}})\] Similarly, denote $q$ is the odd prime divisor of $F_{n+1}$, hence we have $2^{n+2}\mid q-1$. Observe that \[\left\{ \begin{gathered} or{d_p}2 = {2^{n + 1}} \hfill \\ or{d_q}2 = {2^{n + 2}} \hfill \\ \end{gathered} \right. \Rightarrow \left\{ \begin{gathered} {2^{p - 1}} \equiv 1(\bmod q) \hfill \\ {2^{q - 1}} \equiv 1(\bmod p) \hfill \\ \end{gathered} \right.\] It is well-known that $\gcd(F_m,F_n)=1$ for all $m\ne n$, so it is obvious that $p\ne q$. Proof finished. $\square$

If $s=k+1$, why does it follow that $ p\equiv 1 (\bmod 2^{k+1}) $ ?

$\Phi_m(x)=\prod_{d|m}(x^d-1)^{\mu(m/d)}.$

can you please be more explicit, or can you please give me an article for explaining more about $ \Phi_{m}(x) $ ?

Go through Cyclotomic polynomial properties.

drEdrE wrote: If $s=k+1$, why does it follow that $ p\equiv 1 (\bmod 2^{k+1}) $ ? It's the basic property of the order of one element, go search on wikipedia

Am i wrong? suppose that $q$ is an odd prime number $\implies$ $q|2^{q-1}-1$ . assume that : $p_1^{\alpha_1}.p_2^{\alpha_2}...p_{\ell}^{\alpha_{\ell}}$ $=$ $2^{q-1}-1$ $\implies$ $q|2^{q-1}-1|{(2^{p_1-1}-1)}^{\alpha_1}...{(2^{p_\ell-1}-1)}^{\alpha_\ell}$ $\implies$ $\exists_{{p_i}\in(p_1,p_2,...,p_{\ell})}$ such that $q|2^{p_i-1}-1$ $\implies$ $p_i|2^{q-1}-1$ and $q|2^{p_i-1}-1$ . so done

JRD wrote: Am i wrong? suppose that $q$ is an odd prime number $\implies$ $q|2^{q-1}-1$ . assume that : $p_1^{\alpha_1}.p_2^{\alpha_2}...p_{\ell}^{\alpha_{\ell}}$ $=$ $2^{q-1}-1$ $\implies$ $q|2^{q-1}-1|{(2^{p_1-1}-1)}^{\alpha_1}...{(2^{p_\ell-1}-1)}^{\alpha_\ell}$ $\implies$ $\exists_{{p_i}\in(p_1,p_2,...,p_{\ell})}$ such that $q|2^{p_i-1}-1$ $\implies$ $p_i|2^{q-1}-1$ and $q|2^{p_i-1}-1$ . so done Maybe ${p_i}=q$.

yunxiu wrote: JRD wrote: Am i wrong? suppose that $q$ is an odd prime number $\implies$ $q|2^{q-1}-1$ . assume that : $p_1^{\alpha_1}.p_2^{\alpha_2}...p_{\ell}^{\alpha_{\ell}}$ $=$ $2^{q-1}-1$ $\implies$ $q|2^{q-1}-1|{(2^{p_1-1}-1)}^{\alpha_1}...{(2^{p_\ell-1}-1)}^{\alpha_\ell}$ $\implies$ $\exists_{{p_i}\in(p_1,p_2,...,p_{\ell})}$ such that $q|2^{p_i-1}-1$ $\implies$ $p_i|2^{q-1}-1$ and $q|2^{p_i-1}-1$ . so done Maybe ${p_i}=q$. Sorry for my bad mistake.Thanks

ok let p be a divisor of fermat numbers $ P | F_{n} , F_{n}=2^{2^n}+1 \implies p=2^{n+2}k+1 $ and let $ q $ be adivisor of $ F_{n-1} \implies q=2^{n+1}s+1 $ $ 2^{n+1} | q-1 \implies F_{n} | 2^{q-1}-1 \implies p | F_{n} | 2^{q-1}-1 $ $ q | F_{n-1} | 2^n-1 | 2^{p-1}-1 $ and we are done.

There is also an interesting "solution" that depends on the existence of infinitely many primes $r$ s.t. $2^r-1$ is composite (which is unknown). It is a well-known lemma that if $p|2^r-1$, then $p\equiv 1 (mod r)$. Then take $p$ and $q$ that divide $2^r-1$. We have $p,q\equiv 1 (mod r)$, then $r|p-1 \Rightarrow q|2^r-1|2^{p-1}-1$ and $r|q-1 \Rightarrow p|2^r-1|2^{q-1}-1$.

As a corollary, there are infinitely many composite numbers $n$ such that $n\mid 2^n-2$. (This can also be proven starting from the base case $n=17\cdot257$ and noting $n\mid 2^n-2$ implies $2^n-1\mid 2^{2^n-1}-2$.)

$ Lemma 1$: $2^{2^n}+1$ cannot be a power $>1$ of an integer. (Solution do yourself.) $Lemma2$: $Gcd(F_m,F_n)=1$, where $m,n$ are distinct. (Solution do yourself.) According to the lemma1, Let $2^{2^n}+1=p^rs$, where $p$ is prime and $s$ is an integer such that $(s,p)=1$, ($s$ can be $1$) , then by other lemma if $ p|2^{2^n}+1$ then $2^{n+1}|p-1$ . If $s=1$ then let $q$ be a prime divisor of $2^{2^{n+1}}+1$ then $2^{n+2}|q-1$ hence $q|2^{p-1}-1$ and $p|2^{q-1}-1$, so done. If $s>1$ then let $q$ be a prime divisor of $s$, then $q|2^{2^n}+1$, so by $2^{n+1}|p-1$ we also have $2^{n+1}|q-1$. Hence $q|2^{2^n}+1|2^{2^{n+1}}-1|2^{p-1}-1$ and also $p|2^{2^n}+1|2^{2^{n+1}}-1|2^{q-1}-1$, so we done. In conclusion (by lemma2) we can construct an infinite sequence $(k=3,4,5...)$ of primes $(p_k,q_k)$ (where $p_k|2^{2^k}+1$ and $q_k|(2^{2^k}+1)$ or $q|(2^{2^{k+1}}+1)$ so that $p_k|2^{q_k-1}-1$ and $q_k|2^{p_k-1}-1$.

rightways wrote: Let $2^{2^n}+1=ps$, where $p$ is prime and $s$ is an integer such that $(s,p)=1$ A tiny correction: $ 2^{2^n}+1=p^{2k+1}s $. Or do you claim that Fermat numbers are square-free?

dizzy wrote: rightways wrote: Let $2^{2^n}+1=ps$, where $p$ is prime and $s$ is an integer such that $(s,p)=1$ A tiny correction: $ 2^{2^n}+1=p^{2k+1}s $. Or do you claim that Fermat numbers are square-free? Yes, see lemma 1

Rust wrote: For $p=5$ we found $q|\Phi_4(2)=5$. But for $p>5$ we always found $q>p$. How do we know this mr.Rust?

Let p is prime and q is prime divisor of $\Phi_{p-1}(2)$. Then $q|\Phi_{p-1}(2)|2^{p-1}-1$ and $p-1|q-1\to p|2^{q-1}-1$ and $q\ge p$. Therefore we need only there are infinetely many p, suth that exist $p<q|\Phi_{p-1}(2)$. Obviosly if $r=ord_p(2)$ is odd, then for any $q|\Phi_{p-1}(2)\to q\not =p$. We can take any odd r, any prime divisor $p|\Phi_r(2)$ and any prime divisor $q|\Phi_{p-1}(2)$.

Okay. I got it. Thanks.

Why does $p - 1|q - 1$ Mr. Rust? Why not $p|q - 1$?

JRD wrote: Am i wrong? suppose that $q$ is an odd prime number $\implies$ $q|2^{q-1}-1$ . assume that : $p_1^{\alpha_1}.p_2^{\alpha_2}...p_{\ell}^{\alpha_{\ell}}$ $=$ $2^{q-1}-1$ $\implies$ $q|2^{q-1}-1|{(2^{p_1-1}-1)}^{\alpha_1}...{(2^{p_\ell-1}-1)}^{\alpha_\ell}$ $\implies$ $\exists_{{p_i}\in(p_1,p_2,...,p_{\ell})}$ such that $q|2^{p_i-1}-1$ $\implies$ $p_i|2^{q-1}-1$ and $q|2^{p_i-1}-1$ . so done This idea gives a solution: Assume that none of $p_i$ is distinct from$q$ then it means all are $q$ so, in fact, $2^{q-1}-1=q^a$ which from Zigmondy theorem is impossible.

Rust wrote: Let p is prime and q is prime divisor of $\Phi_{p-1}(2)$. Then $q|\Phi_{p-1}(2)|2^{p-1}-1$ and $p-1|q-1\to p|2^{q-1}-1$ and $q\ge p$. Therefore we need only there are infinetely many p, suth that exist $p<q|\Phi_{p-1}(2)$. Obviosly if $r=ord_p(2)$ is odd, then for any $q|\Phi_{p-1}(2)\to q\not =p$. We can take any odd r, any prime divisor $p|\Phi_r(2)$ and any prime divisor $q|\Phi_{p-1}(2)$. If $q$ is a prime divisor of $\Phi_{p-1}(2)$ then $q|p-1$ or $p-1|q-1$. How do we omit the case $q | p-1$ here mr.Rust?

Consider any prime $p>7$, and let $q$ be the prime that divides $2^{p-1} - 1$ but no $2^a - 1$ for all $a < p-1$. Note that such a prime exists by Zsigmondy. Now, we have that the order of $2 \pmod q$ is $p-1$, which means that $p-1$ divides $q-1$. This gives us that $p$ divides $2^{q-1} - 1$. Since this applies to all such primes, we are done.

Quote: [Romania TST 7 2009, Problem 3] Show that there are infinitely many pairs of prime numbers $(p,q)$ such that $p\mid 2^{q-1}-1$ and $q\mid 2^{p-1}-1$.

My solution:

Am I correct?

r=gcd(pk-1,qk-1).

I have a question：can we change “2” to any integer “a”≥2？Who can give me an answer？