Compute 6^100 and 5^100 (mod 13): Solving the Mod Problem with Expert Help

  • Context: Undergrad 
  • Thread starter Thread starter krispiekr3am
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around computing \(6^{100} \mod 13\) and \(5^{100} \mod 13\). Participants explore methods for simplifying these calculations using modular arithmetic, particularly referencing Fermat's little theorem and properties of exponents.

Discussion Character

  • Exploratory
  • Technical explanation
  • Mathematical reasoning
  • Homework-related

Main Points Raised

  • One participant suggests using Fermat's little theorem to simplify the calculations.
  • Another participant questions the application of the theorem, particularly regarding the values of \(a\) and \(p\) in the context of \(6^{100} \mod 13\).
  • There is a discussion about the properties of exponents, specifically \(x^a \cdot x^b = x^{a+b}\), and its relevance to working with large exponents.
  • One participant expresses a desire for a direct answer to work backward from, indicating uncertainty about their own methods.
  • Another participant emphasizes that simply providing the answer does not validate the method used to obtain it.
  • One participant calculates \(6^{100} \mod 13\) to be 9 and \(5^{100} \mod 13\) to be 1, but this is met with skepticism regarding the method used.
  • Another participant critiques the use of Excel for calculations, suggesting that it overlooks the modular properties that limit the need for large exponentiation.
  • A later reply discusses the unnecessary complexity of using higher powers when the results can be derived from known lower powers of 6 modulo 13.

Areas of Agreement / Disagreement

Participants express differing views on the methods for calculating the modular exponentiation, with some advocating for theoretical approaches while others rely on computational methods. There is no consensus on the correctness of the results presented, and the discussion remains unresolved regarding the best approach.

Contextual Notes

Participants highlight the importance of understanding modular arithmetic properties, particularly that calculations can often be simplified by recognizing periodicity in powers, especially when the modulus is prime.

krispiekr3am
Messages
23
Reaction score
0
compute 6^100 (mod 13).
Compute 5^100 (mod 13).
 
Physics news on Phys.org
What have you tried so far? First hint is to make use of Fermat's little theorem.
 
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
 
What is (x^a)*(x^b)? (Forget mod at the moment.)
 
x^(a*b)?
i don't quiet understand or how that help us.
 
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.)
 
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
 
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?
 
krispiekr3am said:
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.
 
  • #10
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:
  • #11
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
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
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
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.
 

Similar threads

MHB What Integers Between -100 and 400 Satisfy Specific Modular Conditions?
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Modulo and Modulus in math and computer programming
  • · Replies 5 ·
Replies
5
Views
3K
Graduate Number of unequal integers with sum S
  • · Replies 12 ·
Replies
12
Views
2K
Why are Mod-10 & Mod-5 decade counters while Mod-6 & Mod-8 not?
  • · Replies 10 ·
Replies
10
Views
5K
Undergrad How Does the Equation D x E mod Φ(N) = 1 Relate to RSA Encryption?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad What is the Best Strategy for the 100 Prisoner Problem?
  • · Replies 6 ·
Replies
6
Views
2K
Modular Arithmetic: Solving Equations with 22x^2 = 11 mod 13
  • · Replies 4 ·
Replies
4
Views
2K
High School Why is -101 mod 13 = 3 and not 10
  • · Replies 5 ·
Replies
5
Views
5K
Factor the repunit ## R_{6}=111111 ## into a product of primes
  • · Replies 3 ·
Replies
3
Views
2K
High School Solving Modular Arithmetic Problems: How to Explained
  • · Replies 3 ·
Replies
3
Views
3K