Online Course Discussion Forum

NT 6.30 MCIIA

 
 
Picture of Alex Gou
NT 6.30 MCIIA
by Alex Gou - Tuesday, April 19, 2022, 7:11 PM
 

I'm having a little trouble understanding the solution for 6.30.

Thanks

 
Picture of John Lensmire
Re: NT 6.30 MCIIA
by John Lensmire - Wednesday, April 20, 2022, 9:50 AM
 

The claim is that if $l$ is a positive odd integer and $n = (p-1)^l$, then $n\cdot 2^n + 1\equiv 0 \pmod{p}$ (for a prime $p$). Note that if this works for any $l$, then we've found infinitely many $n$.

Let's break it down piece by piece. First, $$(p-1)\equiv -1 \pmod{p} \Rightarrow (p-1)^l \equiv (-1)^l \equiv -1 \pmod{p}$$ as $l$ is odd. Next, by Fermat's Little Theorem, $2^{p-1} \equiv 1 \pmod{p}$. Thus, as $(p-1)^l$ is clearly a multiple of $p-1$, we have $$2^{(p-1)^l} \equiv 1 \pmod{p}.$$ Putting it all together, $$n\cdot 2^n + 1\equiv (-1)\cdot 1 + 1 \equiv 0 \pmod{p}$$ as needed.

Hope this helps!