Let $p$ be a prime number and $k,r$ are positive integers such that $p>r$. If $pk+r$ divides $p^p+1$ then prove that $r$ divides $k$.
Problem
Source: Kazakhstan 2020 National 9 grade
Tags: number theory proposed, Kazakhstan, order of an element, number theory, prime numbers
08.08.2020 17:08
A good one. Recall the well-known fact (whose proof I leave you, and it can be easily done using orders): if a prime $q$ divides $p^p+1$ then either $q\mid p+1$ or $2p\mid q-1$. Now, let \[ d={\rm gcd}\left(pk+r,\frac{p^p+1}{p+1}\right). \]If $d=1$ then $pk+r\mid p+1$, that is $k=r=1$, which we have the claim. Suppose $d>1$. Then any prime divisor of $d$ is congruent to $1$ modulo $p$, i.e. $d=p\ell+1$ for some $\ell$. Now let $pk+r = dt$, where $t\in\mathbb{N}$. It then follows that $t\mid p+1$. Furthermore, $dt\equiv r\pmod{p}$. Since $d\equiv 1\pmod{p}$, it thus follows that $t\equiv r\pmod{p}$. Now if $t=p+1$ then $r=1$ (as $r<p$) which gives the desired result. Suppose, therefore, that $t\le p$. Then $t\equiv r\pmod{p}$. Since $t,r\le p$, it then follows $t=r$. Thus, $pk+r = (p\ell+1)r = p\ell r+r$. This yields $k=\ell r$, hence $r\mid k$ as desired.
09.08.2020 01:38
Let $q$ be a prime divisor of $p^p+1$ thus $p^p\equiv -1\mod q$ $$p^{2p}\equiv 1\mod q$$So $ord_q(p)\in\{2,2p\}$ if it is $2$ so $p^2\equiv 1\mod q$ but since $p\neq 1\mod q$ (By $ord_q(p)=2$) we get $q\mid p+1$. If it is $2p$ by $FLT$ we get $2p\mid q-1$. Let $N=pk+r=\prod q_i^{\alpha_i}$. If all the primes of $N$ are $1\mod 2p$ this means $N\equiv r\equiv 1\mod p$ but since $p>r$ this means $r=1$ and indeed $1\mid k$. So let us assume $n\ge 1$ prime divisors $q_i$ of $N$ are such that $q_i\mid p+1$. So $N\equiv r-k\equiv 0\mod q_i$ this means $r\equiv k\mod q_i$. If $p+1=q_j$ for some $j$ we have $r=1$ easy. Assume $p>q_i~\forall i:q_i\mid p+1$ and notice $N\equiv r\equiv \prod_{ i:q_i\mid p+1} q_i\mod p$ but notice that since $q_i\mid p+1$ and each $q_i$ is prime obviously relatively prime to the other it follows $\prod_{i:q_i\mid p+1} q_i\mid p+1$ so we easily get $r=\prod_{i:q_i\mid p+1} q_i$. And since $r\equiv k\mod q_i$ we get the desired result.