Solution to x^k=b mod m Using Prime Factors and Mod Congruence

  • Context: Graduate 
  • Thread starter Thread starter lifom
  • Start date Start date
Click For Summary
SUMMARY

The discussion confirms that if \( x \equiv c \mod p_i \) is a solution to \( x^k \equiv b \mod p_i \) for distinct primes \( p_1, p_2, \ldots, p_r \), then it follows that \( x \equiv c \mod m \) is a solution to \( x^k \equiv b \mod m \), where \( m \) is the product of these primes. This conclusion is based on the Chinese Remainder Theorem, which states that if two numbers are congruent modulo coprime integers, they are congruent modulo the product of those integers. The gcd condition is crucial for this deduction.

PREREQUISITES
  • Understanding of modular arithmetic
  • Familiarity with the Chinese Remainder Theorem
  • Knowledge of prime factorization
  • Basic concepts of greatest common divisor (gcd)
NEXT STEPS
  • Study the Chinese Remainder Theorem in detail
  • Explore applications of modular arithmetic in cryptography
  • Learn about prime factorization techniques
  • Investigate gcd algorithms and their implications in number theory
USEFUL FOR

Mathematicians, computer scientists, and anyone interested in number theory, particularly those working with modular equations and cryptographic applications.

lifom
Messages
14
Reaction score
0
Let m be a product of distinct primes p1,p2,...pr.
Assume x=c (mod pi) is a solution of x^k=b (mod pi) for all i =1,2,3,...r.
Can I conclude that x=c (mod m) is a solution of x^k=b (mod m) ?

(I think that if a=b mod x and a=b mod y then a=b mod(xy), provided that gcd(x,y)=1)
 
Physics news on Phys.org
lifom said:
Can I conclude that x=c (mod m) is a solution of x^k=b (mod m) ?

Yes.
 

Similar threads

  • · Replies 3 ·
Replies
3
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
5K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
4K
  • · Replies 6 ·
Replies
6
Views
8K
  • · Replies 11 ·
Replies
11
Views
2K
  • · Replies 5 ·
Replies
5
Views
7K
  • · Replies 3 ·
Replies
3
Views
4K
  • · Replies 7 ·
Replies
7
Views
3K