$(MON 4)$ Let $p$ and $q$ be two prime numbers greater than $3.$ Prove that if their difference is $2^n$, then for any two integers $m$ and $n,$ the number $S = p^{2m+1} + q^{2m+1}$ is divisible by $3.$
Problem
Source:
Tags: modular arithmetic, number theory, Divisibility, IMO Shortlist, IMO Longlist
Goutham
04.10.2010 09:18
My solution: Since their difference is not divisible by $3$, we have $p, q$ to be distinct non zero residues modulo $3$ which means $p^{2m+1}+q^{2m+1}\equiv 2^{2m+1}+1\equiv 4^m\cdot 2+1\equiv 0\pmod 3$ as required.
Ovchinnikov Denis
04.10.2010 10:13
gouthamphilomath wrote: $(MON 4)$ Let $p$ and $q$ be two prime numbers greater than $3.$ Prove that if their difference is $2^n$, then for any two integers $m$ and $n,$ the number $S = p^{2m+1} + q^{2m+1}$ is divisible by $3.$ With such condition more powerful: Let $k=ord_3 (2m+1)$ (maximum power of 3 which divides $2m+1$) Prove that $3^{k+1}|p^{2m+1}+q^{2m+1}$ (1).
easy by induction to $k$.
Base for $k=0$ was already proved:
gouthamphilomath wrote:
My solution: Since their difference is not divisible by $3$, we have $p, q$ to be distinct non zero residues modulo $3$ which means $p^{2m+1}+q^{2m+1}\equiv 2^{2m+1}+1\equiv 4^m\cdot 2+1\equiv 0\pmod 3$ as required.
So we must prove that (1) for $k+1$ (we know it for $k$).
Let $2m+1=3^{k+1}x$ where $gcd(x;2)=gcd(x;3)=1$.
$gcd(p;3)=gcd(q;3)=gcd(p-q;3)=1$=> $(p\equiv 1 ; q \equiv 2 )$ or $(p \equiv 2; q \equiv 1)$ ($mod3$).
WLOG, $p\equiv 1 ; q \equiv 2 $($mod3$).
Then $p^{3^{k+1}x}+q^{3^{k+1}x}=(p^{3^kx}+q^{3^kx})( \bigl( p^{3^kx} \bigr)^2- p^{3^kx}q^{3^kx}+\bigl( q^{3^kx} \bigr) ^2)$. by induction, we know, that $p^{3^kx}+q^{3^kx}$ divides by $3^{k+1}$ so we need to prove, that $\bigl( p^{3^kx} \bigr)^2- p^{3^kx}q^{3^kx}+\bigl( q^{3^kx} \bigr) ^2$ divides by $3$. But $p^{3^kx} \equiv 1; q^{3^kx} \equiv 2$($mod3$)=>$\bigl( p^{3^kx} \bigr)^2- p^{3^kx}q^{3^kx}+\bigl( q^{3^kx} \bigr) ^2 \equiv 2^2-2*1+1 \equiv 0$($mod3$) => induction is end =>
QED