# modulo arithmetic help

• Nov 17th 2013, 08:21 AM
Tweety
modulo arithmetic help
I am really having trouble understanding how to do these questions, and I have read up on google, but still struggling

\$\displaystyle 5^{11} mod 9 = ? \$

I need to be able to do this question without a calculator, and i am not sure how to do it? Any help appreciated.
• Nov 17th 2013, 03:22 PM
chiro
Re: modulo arithmetic help
Hey Tweety.

The easiest way to do this is to use powers of 2. Look at 5 mod 11, then 5^2, then 5^4, 5^8, then 5^10 and finally 5^11.

As an example 5 mod 9 = 5. 5^2 mod 9 = 25 mod 9 = -2. 5^4 = (-2)^2 mod 9 = 4. 5^8 mod 9 = 16 mod 9 = -2. 5^11 mod 9 = -2*-2*5 mod 9 = 20 mod 9 = 2.

Check to see if I have made a mistake, but the process used above is the basic idea in solving these kinds of problems.
• Nov 18th 2013, 05:49 AM
Hartlw
Re: modulo arithmetic help
Using modular arithmetic of remainder classes: [a][b]=[ab]:

[5][5]=[25]=[7]
[5]3=[35]=[8]
[5]4=[40]=[4]
[5]5=[20]=[2]
[5]11=[2][2][5]=[20]=[2]
• Nov 18th 2013, 10:20 AM
Tweety
Re: modulo arithmetic help
Quote:

Originally Posted by chiro
Hey Tweety.

The easiest way to do this is to use powers of 2. Look at 5 mod 11, then 5^2, then 5^4, 5^8, then 5^10 and finally 5^11.

As an example 5 mod 9 = 5. 5^2 mod 9 = 25 mod 9 = -2. 5^4 = (-2)^2 mod 9 = 4. 5^8 mod 9 = 16 mod 9 = -2. 5^11 mod 9 = -2*-2*5 mod 9 = 20 mod 9 = 2.

Check to see if I have made a mistake, but the process used above is the basic idea in solving these kinds of problems.

Hello,

Thank you, this is the methos my teacher showed me, but i still couldnt quite get the hang of it,

please tell me if this working out is correct, thank you.

\$\displaystyle 5^{1} mod 9 = 5 \$

\$\displaystyle 5^{2} mod 9 = 7 \$

\$\displaystyle 5^{4} mod 9 = (5^{2})^{2} mod 9 = 49 mod 9 = 4 \$

\$\displaystyle 5^{8} mod 9 = (5^{4}) mod 9 = (4)^{2} mod 9 = 16 mod 9 = 7 \$

so \$\displaystyle 5^{11} mod 9 = 5^{1} . 5^{2} . 5^{8} mod 9 = 7 . 7 . 5 = 245 mod 9 \$

9 x 27 = 243

so 245/9 = 27

remainder = 2

so 245 mod 9 = 2?