Thread: Two quick questions

1. Two quick questions

These are stumping me for some odd reason...

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

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

2. Hello, Aryth!

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

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

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

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

$\displaystyle \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: .$\displaystyle 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 $\displaystyle \left(\frac{-1}{151} \right)=-1,$ the equation $\displaystyle x^2 \equiv -1 \mod 151$ has no solution and thus, obviously, $\displaystyle x^{10} \equiv -1 \mod 151$ cannot have any solution either.

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

6. I seriously appreciate the help.