1. ## 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.

2. ## 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.

3. ## 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]

4. ## Re: modulo arithmetic help

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?