This is a very interesting word problem that I came across in an old textbook of mine. So I mused over this problem for a while and tried to look at the different ways to approach it but unfortunately I was confused by the problem and I don't really understand how to do it either, hence I am unable to show my own working or opinion. The textbook gave a hint about using Fermat's little theorem but I don't really understand it and I'm really not sure about how to approach it. Any guidance hints or help would be truly greatly appreciated. Thanks in advance 🙂 So anyway, here the problem goes: (It is composed of three parts)
$a)$ Determine the remainder when $2^{2017}+1 $ is divided by $17$.
$b)$ Prove that $30^{99} + 61^{100}$ is divisible by $31$.
$c)$ It is known that numbers $p$ and $8p^2 + 1 $ are primes. Find $p$.
Best Answer
In problem (a), use Fermat's little theorem, which says (or a rather, a very slightly different version says) that for any prime number $p$, and any integer $n$ that's not divisible by $p$, we have $$n^{p-1}\equiv 1\bmod p$$ In particular, use $n=2$ and $p=17$. Keep in mind that $2017=(126\times 16)+1$.
In problem (b), note that $30\equiv 61\equiv -1\bmod 31$ (you don't even have to use Fermat's little theorem here).
In problem (c), use Andre's hint above: if $p$ is any prime number other than $3$, then $p^2\equiv 1\bmod 3$ (which you can see is an application of Fermat's little theorem). What does that mean $8p^2$ is congruent to modulo $3$? What does that mean $8p^2+1$ is congruent to modulo $3$? Can a prime number be congruent to that modulo $3$?