Two quick questions

**Aryth** · May 6th 2009, 05:32 AM

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)

**Soroban** · May 6th 2009, 06:04 AM

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

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

**Aryth** · May 6th 2009, 12:39 PM

Would anyone be able to help with the second one?

**NonCommAlg** · May 6th 2009, 12:47 PM

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.

**NonCommAlg** · May 6th 2009, 02:11 PM

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!

**Aryth** · May 9th 2009, 11:06 AM

I seriously appreciate the help.

Thread: Two quick questions

LinkBack

Thread Tools

Display

Two quick questions

Similar Math Help Forum Discussions

Two quick questions.

Two Not So Quick Questions

two quick questions

Some quick questions

3 Quick Questions

Search Tags