Cool Number Theory
- Souvik saha
- Posts:6
- Joined:Sat Apr 13, 2013 12:47 pm
- Location:Mymensingh, Dhaka, Bangladesh
- Contact:
Find all prime numbers $p$ and $q$ such that $pq$ divides the product $(5^p-2^p)(5^q-2^q)$.
Re: Cool Number Theory
There are primes as powers,primes as divisors-I can't think of sth else than Fermat' Little Theorem!
Let us assume,by symmetry,that $p\leq q$. Now $p|(5^p-2^p)$ or $p|(5^q-2^q)$.
By Fermat's theorem,if a prime $p$ divides $5^p-2^p$,then $5^p-2^p\equiv 5-2\equiv 3\equiv 0\Rightarrow p=3$. Applying this fact we get a solution $(p,q)=(3,3)$. Now we assume $p>3$. So $p|(5^q-2^q)$.
Now $5^q\equiv 2^q(mod p)$ and by Fermat's, $5^{p-1}\equiv 2^{p-1}(mod p)$ so by a well-known(and useful) lemma, $5^{gcd(q,p-1)}\equiv 2^{gcd(q,p-1)}(mod p)$. But $p-1<p\leq q$ so $gcd(q-1,p)=1$ and so $p|(5-2)=3$ i.e. $p=3$ a contradiction to our assumption $p>3$.
Thus $p=3$ if $p|(5^q-2^q)$. As we let $q>3$,we have $q|(5^3-2^3)=117$ i.e. $q=13$. By symmetry we have found another two solutions $(3,13),(13,3)$.
Let us assume,by symmetry,that $p\leq q$. Now $p|(5^p-2^p)$ or $p|(5^q-2^q)$.
By Fermat's theorem,if a prime $p$ divides $5^p-2^p$,then $5^p-2^p\equiv 5-2\equiv 3\equiv 0\Rightarrow p=3$. Applying this fact we get a solution $(p,q)=(3,3)$. Now we assume $p>3$. So $p|(5^q-2^q)$.
Now $5^q\equiv 2^q(mod p)$ and by Fermat's, $5^{p-1}\equiv 2^{p-1}(mod p)$ so by a well-known(and useful) lemma, $5^{gcd(q,p-1)}\equiv 2^{gcd(q,p-1)}(mod p)$. But $p-1<p\leq q$ so $gcd(q-1,p)=1$ and so $p|(5-2)=3$ i.e. $p=3$ a contradiction to our assumption $p>3$.
Thus $p=3$ if $p|(5^q-2^q)$. As we let $q>3$,we have $q|(5^3-2^3)=117$ i.e. $q=13$. By symmetry we have found another two solutions $(3,13),(13,3)$.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$