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.

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]

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?