Congruences, Fermats Little Theorm

  • Thread starter Nebula
  • Start date
In summary, to solve the first problem, we can use Fermat's Little Theorem to simplify the equation to 9^794 == 8 (mod 73). For the second problem, we can use the same theorem to simplify the equation to X^86 == 6 (mod 29). This should provide a starting point for solving both equations.
  • #1
Nebula
46
0
Can someone explain how to solve these types of things, my book gives one example and its useless:

find a such that 0 < a < 73
a=9^794(mod 73) (= means congruent equals)

solve
x^86=6(mod 29)

Thanks in advance :smile:
 
Physics news on Phys.org
  • #2
In the equation X^86 ==6 Mod 29, we note that for X not 0, X^28==1, by Fermat's Little Theorem. Thus X^86 ==X^28*X^28*X^28*X^2 ==X^2==6 Mod 29. That should be a start on the problem.
 
  • #3
For the first problem :

You could start from the ground up :

9^2 = 81== 8 (mod 73) => 9^4 == 64 == -9 => 9^8==81==8...(lucky!) and so on, but you don't have to, because 73 is prime and does not divide 9. So you can happily use the Little Theorem.

ie: 9^72 == 1 (mod 73) => (9^72)^n == 1^n = 1 (mod 73), for any n. With n=11, you get 9^792==1 (mod 73).

So 9^794 == 9^2 (mod 73)
 
Last edited:

1. What are congruences?

Congruences are a mathematical concept that describes the relationship between two numbers. Two numbers are considered congruent if they have the same remainder when divided by a certain number. For example, 12 and 22 are congruent modulo 5 because they both have a remainder of 2 when divided by 5.

2. What is Fermat's Little Theorem?

Fermat's Little Theorem is a fundamental theorem in number theory that states that if p is a prime number, then for any integer a, a^p is congruent to a modulo p. This means that a^p and a have the same remainder when divided by p. This theorem has many applications in number theory and cryptography.

3. How is Fermat's Little Theorem used in cryptography?

Fermat's Little Theorem is used in the RSA encryption algorithm, which is widely used in modern cryptography. The theorem provides a way to generate large prime numbers, which are essential for secure encryption. The security of RSA relies on the fact that it is difficult to factor large numbers into their prime factors.

4. Can Fermat's Little Theorem be extended to non-prime moduli?

Yes, there is a generalization of Fermat's Little Theorem called Euler's Theorem, which states that if a and n are relatively prime integers, then a^phi(n) is congruent to 1 modulo n, where phi(n) is Euler's totient function. This theorem can be used with non-prime moduli, but the calculation of phi(n) can be more complex.

5. How is Fermat's Little Theorem related to Euler's Totient Function?

Fermat's Little Theorem is a special case of Euler's Totient Function. When n is a prime number, the value of phi(n) is n-1, making Fermat's Little Theorem a specific case of Euler's Theorem. However, when n is not prime, the value of phi(n) is a more complex calculation, and the relationship between the two theorems is not as straightforward.

Similar threads

Replies
5
Views
1K
  • General Math
Replies
1
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
5K
  • Calculus and Beyond Homework Help
Replies
17
Views
3K
  • General Math
Replies
4
Views
2K
  • Math Proof Training and Practice
3
Replies
93
Views
10K
  • Calculus and Beyond Homework Help
Replies
1
Views
844
Replies
1
Views
787
  • Math Proof Training and Practice
Replies
25
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
3K
Back
Top