Let $p$ be a prime number such that $\frac{28^p-1}{2p^2+2p+1}$ is an integer. Find all possible values of number of divisors of $2p^2+2p+1$.
Problem
Source: Turkey National Mathematical Olympiad 2020 P4
Tags: number theory, prime numbers, number theory proposed
electrovector
08.03.2021 15:26
Only possible value is $2$. Take $p=7$.
Let's take a prime $q$ such that $q|2p^2+2p+1$ and clearly $q| 28^p-1$. It is clear that $q \equiv 1 \pmod{4}$. Thus $gcd(28, q)=1$ and $28^{q-1} \equiv 1 \pmod{q}$. We can easily find that $ord_q(28)$ must be either $p$ or $1$. However if order equals to $1$ we will have $q=3$, contradiction. So order must be $p$ and $p|q-1 \Rightarrow q \ge p+1$. For some $q$ prime if we had $v_q(2p^2+2p+1) \ge 3$, $2p^2+2p+1$ would be greater than $(p+1)^3$ which clearly results in a contradiction. From the same reason we can find that $2p^2+2p+1$ cannot have more than $3$ distinct prime divisors. So we are left with cases $2p^2+2p+1=qr$, $2p^2+2p+1=q^2$ and $2p^2+2p+1=q$ where $q$ and $r$ are distinct primes. For $2p^2+2p+1=q$ we have already found an equality case. If $2p^2+2p+1=q^2$, since we can write $q=pk+1$, we would have $2p^2+2p+1=(pk+1)^2=p^2k^2+2pk+1 \Rightarrow 2p+2=pk^2+2k$. It can be easily seen that $k$ must be $1$ and this gives us a contradiction as well. Hence we are left with case $2p^2+2p+1=qr$ and because of same reasoning, we have $2p^2+2p+1 =(pk+1)(pm+1) =p^2mk+p(m+k)+1 \Rightarrow 2p+2=pmk+m+k$. Because $q$ and $r$ are distinct, we have $m$ and $k$ are distinct too and this gives the final contradiction and finishes the problem.
grupyorum
08.03.2021 18:14
@electrovector: Good solution. A shorter alternative. It is evident that for $p=2,3$, $2p^2+2p+1$ does not divide $28^p-1$. Observe that $2p^2+2p+1 =2p(p+1) +1 \in\{1,2\}\pmod{3}$. Now take any prime $q\mid 2p^2+2p+1$. We then have $q\ne 3$. Next, $q\mid 28^p-1$. By Fermat, we also have $28^{q-1}\equiv 1\pmod{q}$. Consequently, $28^{(p,q-1)}\equiv 1\pmod{q}$. Since $p$ is a prime, $(p,q-1)\in\{1,p\}$. In the former, we find $q\mid 27$, which implies $q=3$, a contradiction (with $q\ne 3$). Thus $p\mid q-1$. Then $q=2pk+1$ for some $k\in\mathbb{N}$ (note the factor of two above - recall $p,q$ are odd). With this, we now show $2p^2+2p+1$ must be a prime. If not, then $2p^2+2p+1 \ge (2p+1)^2$, which is a clear contradiction. The equality is achieved for $p=7$ (which I think is messier than the entire reasoning!) The key point is once finding $p\mid q-1$, it suffices to write $q=2pk+1$ since $p,q$ are odd.
Jjesus
07.04.2021 02:02
electrovector wrote:
Only possible value is $2$. Take $p=7$.
Let's take a prime $q$ such that $q|2p^2+2p+1$ and clearly $q| 28^p-1$. It is clear that $q \equiv 1 \pmod{4}$. Thus $gcd(28, q)=1$ and $28^{q-1} \equiv 1 \pmod{q}$. We can easily find that $ord_q(28)$ must be either $p$ or $1$. However if order equals to $1$ we will have $q=3$, contradiction. So order must be $p$ and $p|q-1 \Rightarrow q \ge p+1$. For some $q$ prime if we had $v_q(2p^2+2p+1) \ge 3$, $2p^2+2p+1$ would be greater than $(p+1)^3$ which clearly results in a contradiction. From the same reason we can find that $2p^2+2p+1$ cannot have more than $3$ distinct prime divisors. So we are left with cases $2p^2+2p+1=qr$, $2p^2+2p+1=q^2$ and $2p^2+2p+1=q$ where $q$ and $r$ are distinct primes. For $2p^2+2p+1=q$ we have already found an equality case. If $2p^2+2p+1=q^2$, since we can write $q=pk+1$, we would have $2p^2+2p+1=(pk+1)^2=p^2k^2+2pk+1 \Rightarrow 2p+2=pk^2+2k$. It can be easily seen that $k$ must be $1$ and this gives us a contradiction as well. Hence we are left with case $2p^2+2p+1=qr$ and because of same reasoning, we have $2p^2+2p+1 =(pk+1)(pm+1) =p^2mk+p(m+k)+1 \Rightarrow 2p+2=pmk+m+k$. Because $q$ and $r$ are distinct, we have $m$ and $k$ are distinct too and this gives the final contradiction and finishes the problem.
$2p^2+2p+1=q$?????
Tintarn
07.04.2021 20:35
Jjesus wrote: $2p^2+2p+1=q$????? Please don't quote entire posts if they are long. Also please ask more precisely: What exactly is your criticism of the cited solution? The case $2p^2+2p+1=q$ is mentioned and it is explained that it is the only remaining case whence the result.
Turker31
02.11.2023 13:21
Let a prime divisor of $2p^2 +2p +1$ be a number say $ q $. Then, $q$ must divide $28^p -1$. $28^p \equiv 1 \pmod{q}$. Let $ord_q (28)$ be a number say $ d $. Then, $ d $ must divide $ p $. There are two possibilities : $1)$ : if $ d =1 $, then $28 \equiv 1 \pmod{q}$. Since $27 \equiv 0 \pmod{q}$ and $q$ is a prime number, $q$ must be equal to $3$. So, $3|2p^2 +2p +1$. This is impossible. $2 )$: if $ d =p $, then $p|q-1$. Because, by the fermat's little theorem, $28^{q-1} \equiv 1 \pmod{q}$. If $p|q-1$, write $q$ again like $p \cdot k +1$. In conclusion, we have $p \cdot k +1 | 2p^2 + 2p +1$. With some case work, everyone can see that $ k $ must be equal to $ 2p + 2$. Since, $ k= 2p+2$, $ q = 2p^2 + 2p +1$. We accepted that $ q $ was a prime number. So, $2p^2 + 2p +1$ is a prime number if it divides $28^p -1$. A prime number has just only 2 divisors. The answer is : only 2. $\square$