Two quick questions

Printable View

May 6th 2009, 05:32 AM
Aryth

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)
May 6th 2009, 06:04 AM
Soroban

Hello, Aryth!

Quote:

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 <br />$

Hence: . $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 $\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.
May 6th 2009, 02:11 PM
NonCommAlg

Quote:

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!
May 9th 2009, 11:06 AM
Aryth

I seriously appreciate the help.

All times are GMT -8. The time now is 04:25 AM.