# Fermat's little theorem

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$.

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$?

• For (c), I got confused because I don't particularly understand Andre's hint or your hint. Could you please try to reword it so it is more clear? I don't get how modulo $3$ relates to this, or how the $p^2≡1 \bmod3$ helps solve the problem. – anonymous Jul 7 '15 at 7:49

Hints:

a) $2016$ is divisible by $16$. Now use Fermat's Theorem.

b) $30\equiv -1\pmod{31}$ and $61\equiv -1\pmod{31}$.

c) If the prime $p$ is not equal to $3$ then $p^2\equiv 1\pmod{3}$.

• Maybe for a) it is better to mention that $2^4\equiv -1\pmod{17}$ because the fact that $16 \mid 2016$ is not so obvious as $4\mid 2016$. – user 170039 Jul 5 '15 at 14:08
• @user170039: That is a very good hint. I was thinking in terms of the generic Fermat Theorem calculation, where in finding $a^n$ modulo $p$ one finds the remainder of $n$ on division by $p$. But because of the special relationship between $2$ and $17$ we can bypass the Fermat Theorem. – André Nicolas Jul 5 '15 at 14:15