1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – anonymous Jul 7 '15 at 7:49
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – user 170039 Jul 5 '15 at 14:08
  • $\begingroup$ @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. $\endgroup$ – André Nicolas Jul 5 '15 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.