# Two quick questions

• May 6th 2009, 05:32 AM
Aryth
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)
• May 6th 2009, 06:04 AM
Soroban
Hello, Aryth!

Quote:

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$

• May 6th 2009, 12:39 PM
Aryth
Would anyone be able to help with the second one?
• May 6th 2009, 12:47 PM
NonCommAlg
Quote:

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.
• May 6th 2009, 02:11 PM
NonCommAlg
Quote:

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!
• May 9th 2009, 11:06 AM
Aryth
I seriously appreciate the help.