1. ## Two quick questions

These are stumping me for some odd reason...

1. Find the remainder of $2009^{2008}$ upon division by 9.

2. Determine with explanation, whether there exists an integer n such that $n^{10} + 1$ is divisible by 151. (Note that 151 is prime)

2. Hello, Aryth!

1. Find the remainder of $2009^{2008}$ upon division by 9.

Since $2009 \:=\:223(9) + 2$, then: . $2009 \div 9$ has a remainder of 2.

Then: . $2009^{2008} \div 9$ has a remainder of $2^{2008}$

We find that: . $2^6 \,=\,64$ . . . and $64 \div 9$ has remainder 1.

$\text{Then: }\;2^{2008} \;=\;2^{334(6) + 4} \;=\;2^{334(6)}\cdot 2^4 \;=\;\underbrace{\left(2^6\right)^{334}}_{\text{re m. 1}}\cdot16
$

Hence: . $16 \div 9 \quad\to\quad \text{remainder } 7$

3. Would anyone be able to help with the second one?

4. Originally Posted by Aryth

Would anyone be able to help with the second one?
well, it's quite easy: since $\left(\frac{-1}{151} \right)=-1,$ the equation $x^2 \equiv -1 \mod 151$ has no solution and thus, obviously, $x^{10} \equiv -1 \mod 151$ cannot have any solution either.

5. Originally Posted by NonCommAlg
well, it's quite easy: since $\left(\frac{-1}{151} \right)=-1,$ the equation $x^2 \equiv -1 \mod 151$ has no solution and thus, obviously, $x^{10} \equiv -1 \mod 151$ cannot have any solution either.
another way: suppose $n^{10} \equiv -1 \mod 151$ has a solution. then $n^{150}=(n^{10})^{15} \equiv -1 \mod 151.$ but, since $\gcd(n,151)=1,$ by Fermat's little theorem $n^{150} \equiv 1 \mod 151.$ contradiction!

6. I seriously appreciate the help.