Computing 6^100 and 5^100 modulo 13

[krispiekr3am]

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

 

[shmoe]

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

 

[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

 

[matt grime]

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

 

[krispiekr3am]

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

 

[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.)

 

[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

 

[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?

 

[JasonRox]

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

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.

 

[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)$$

 

[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?

 

[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.

 

[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

 

[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.