# Mod problem. can someone help

1. Oct 19, 2006

### krispiekr3am

compute 6^100 (mod 13).
Compute 5^100 (mod 13).

2. Oct 19, 2006

### shmoe

What have you tried so far? First hint is to make use of Fermat's little theorem.

3. Oct 19, 2006

### krispiekr3am

Fermat's little theorem
is that a^p=a*(mod p)

but we have 6^100 mod13

a=6
p=100

6=6(mod100)?
we want mod 13 though

4. Oct 20, 2006

### matt grime

What is (x^a)*(x^b)? (Forget mod at the moment.)

5. Oct 20, 2006

### krispiekr3am

x^(a*b)?
i dont quiet understand or how that help us.

6. Oct 20, 2006

### matt grime

No, that is not correct. And it does help. Have a ponder on it. If I wanted to work out x^{some really large number}, can I use smaller powers of x to get there? (Yes.)

7. Oct 21, 2006

### krispiekr3am

x^a*x^b
=x^(a+b)
?
can you guys give me the answer and i can work backward? because i can try many ways and will not know its the correct answer or not.
thanks

8. Oct 22, 2006

### matt grime

Just giving you the answer won't mean that the method you get to get the same number is correct or not.

If 6^12=1, mod 13, what is 6^24?

9. Oct 22, 2006

### JasonRox

I would suggest exploring what happens when you have large exponents, but in simple cases.

matt grime points you in the right direction.

Note: Mathematics is about going forward and not backwards.

10. Oct 22, 2006

### murshid_islam

try $$6^{100} \left(\bmod \ 13\right) = \left(6^{12}\right)^8.6^4 \left(\bmod \ 13\right)$$
and $$5^{100} \left(\bmod \ 13\right) = \left(5^{12}\right)^8.5^4 \left(\bmod \ 13\right)$$

Last edited: Oct 22, 2006
11. Oct 23, 2006

### krispiekr3am

I did this using excel

6^100mod13 is equal to 9?

if its right, i think i did it right.

5^100mod13 is equal to 1?

12. Oct 23, 2006

### matt grime

Excel? Why? Did you not pay attention to the hints people have given you? If you raised 6 to the power 100 then reduced mod 13 you did it wrong. There is never any need to raise 6 (or any number coprime to 13) higer than the power 11 because x^12=1 mod 13 for x coprime with 13.

13. Oct 23, 2006

### krispiekr3am

i follow the notes from my class.
the teacher created a chart of
all possible number n, 6^n, 6^n%13.
6^100 = (6^10)^10?
and knowing that 6^10=4
4^10mod13 =9
therefore 6^100mod13=9

n 6^n 6^n % 13
1 6 6
2 36 10
3 216 8
4 1296 9
5 7776 2
6 46656 12
7 279936 7
8 1679616 3
9 10077696 5
10 60466176 4
11 362797056 11
12 2176782336 9

14. Oct 24, 2006

### matt grime

Since you know all of the powers of 6 mod 13, why go to powers of 4? It is completely unnecessary. Further, why, for simplicitly do you use 36 for 6^2, instead of 10? There is never any need to work out powers large than 12 (for mod(13)), and never any need to multiply numbers that are larger than 13 (for mod(13)). Useful to remember if you don't have a calculator, or a computer to use.