Find all triples $(p,q,n)$ that satisfy \[q^{n+2} \equiv 3^{n+2} (\mod p^n) ,\quad p^{n+2} \equiv 3^{n+2} (\mod q^n)\] where $p,q$ are odd primes and $n$ is an positive integer.
Problem
Source:
Tags: modular arithmetic, algebra, polynomial, Vieta, number theory unsolved, number theory
28.11.2010 12:02
Answer: $(3,3,n)$ If any two of $p,q,3$ are equal, it is easy to get the solution $(3,3,n)$. Now assume that $p,q,3$ are pairwise distinct. WLOG assume $p>q$. $p^n|q^{n+2}-3^{n+2}$ and $q^n|p^{n+2}-3^{n+2}$, so $p^nq^n|p^{n+2}+q^{n+2}-3^{n+2}$. $p^nq^n\le p^{n+2}+q^{n+2}-3^{n+2}<2p^{n+2}$, so $q^n<2p^2$ and $p^2>q^{n-1}$. But we have $q^{n+2}-3^{n+2}\ge p^n$, so $q^{n+2}>p^n>q^{n(n-1)/2}$. Thus $n+2>\frac{n(n-1)}2$ and we get $n\le3$. (i) $n=2$ $p^2|q^4-81=(q^2+9)(q+3)(q-3)$. Since $p>q$, then $p\not|q-3$. If $p|q+3$, since $q+3<2p$, then $p=q+3$ which is impossible. Thus $p^2|q^2+9$. Since $q^2+9<2p^2$, then $q^2+9=p^2$ $(p+q)(p-q)=9$ $p+q=9,p-q=1$ $p=5,q=4$ Contradiction. (ii) $n=3$ $p^3|q^5-243$, $q^3|p^5-243$, $p^3q^3|p^5+q^5-243$ If $p=5$ then $q^3|5^5-3^5=2\cdot11\cdot131$, which is impossible. So $p\ne5$ and similarly we get $q\ne5$. Assume that $q|p-3$. Note that $p^3\le q^5-243<q^6$, so $p<q^2$. So $p-3$ is not divisible by $q^2$. We have $q^3|p^5-243$, so $q|p^4+3p^3+9p^2+27p+81$ $0\equiv p^4+3p^3+9p^2+27p+81\equiv5\cdot3^4\pmod{q}$ Thus $q=3$ or $5$, which is impossible. Therefore $q\not|p-3$ and similarly $p\not|q-3$. From $p^5\equiv 3^5\pmod{q}$ and Fermat, we get $p^{(q-1,5)}\equiv3^{(q-1,5)}\pmod{q}$. Since $p\not\equiv3\pmod{q}$, then $(q-1,5)=5$, thus $5|q-1$ and similarly $5|p-1$. So $p,q\ge11$. $p^3\le q^4+3q^3+9q^2+27q+81\le q^4+\frac3{11}q^4+\frac9{121}q^4+\frac{27}{1331}q^4+\frac{81}{14641}q^4<1.4q^4$. $\frac{p^5+q^5-243}{p^3q^3}<\frac{p^2}{q^3}+\frac{q^2}{p^3}<\frac{p^2}{(\frac{p^3}{1.4})^{3/4}}+\frac1p<1$ a contradiction with $p^3q^3|p^5+q^5-243$.
28.11.2010 21:30
I will use tricky lemma to show that $(p,q,n)=(3,3,n)$ is the only solution.First let $p=q.$,then $p^n|p^{n+2}-3^{n+2}$ implies $p=q=3$ and obviously true for all $n$.Now let wlog say $p>q$.Then $p^n|q^{n+2}-3^{n+2}$ and from tricky lemma,it follows that $p^n|n+2$.Because $q-3<p,gcd(p,q-3)=1$.But for $n\ge 2,p^n>n+2$ (except trivial case) since $p>2$.When $n=1,p|3$ or $p=3$.But then $q=2$ because $q<p$,a contradiction for $p,q$ odd prime.
29.11.2010 06:54
mathmdmb wrote: Then $p^n|q^{n+2}-3^{n+2}$ and from tricky lemma,it follows that $p^n|n+2$. The lemma works if $p|q-3$.
03.06.2011 11:49
sorry .... the case to $ n =1 $ is to be considered as well but which can be treated similarly ....
26.03.2013 12:01
I also obtained that if $ n \geq 2 $ the only solution is $ 3,3 $ but for $ n=1 $ I'm stuck. after some manipulations it is equivalent with $ pq|p^{2}+q^{2}+3p+3q+9 $. using vieta jumping to solve this equation I obtained that $ RHS=17LHS $ and that $ p<q,(p,q)=(x_{m},x_{m+1}) $ for some $ m $ where $ x_{0}=1,x_{1}=1,x_{n+1}=17x_{n}-x_{n-1}-3 $... how can we solve this case?
25.09.2016 15:21
Lei Lei wrote: Find all triples $(p,q,n)$ that satisfy \[q^{n+2} \equiv 3^{n+2} (\mod p^n) ,\quad p^{n+2} \equiv 3^{n+2} (\mod q^n)\]where $p,q$ are odd primes and $n$ is an positive integer. In official paper ,the problem is that $n$ is a positive integer which is larger than $1$ ! Can anyone help to fix it?
29.10.2018 18:31
I guess to solve this for $n=1$ is fairly hopeless because I have found the following example. \[ p = 4030880685300934533537836536908567840906979698702338335802261461984751241690632767946539048169605938107198771021922895868463498909767986096425295082411439356431524073331754677148268650672471186540413607215603179506111936434633260511233 \](235 digits) \[ q= 68287034842100981751539318023770648704999043734113530745824391223028362895417385332881467871943703856419761214944101468316269029221579562026497580217157468863914922542415581137125851722077039962556575891158873780132243319683087671382017\](236 digits) PS1. For user's convenience, I attach a text for those values below; p= 4030880685300934533537836536908567840906979698702338335802261461984751241690632767946539048169605938107198771021922895868463498909767986096425295082411439356431524073331754677148268650672471186540413607215603179506111936434633260511233 q= 68287034842100981751539318023770648704999043734113530745824391223028362895417385332881467871943703856419761214944101468316269029221579562026497580217157468863914922542415581137125851722077039962556575891158873780132243319683087671382017 PS2. For searching the numbers, I have used anonymouslonely's sequence. Thanks for him/her.