Solution to the general congruence

  • Context: Undergrad 
  • Thread starter Thread starter eljose
  • Start date Start date
  • Tags Tags
    General
Click For Summary
SUMMARY

The discussion focuses on solving the general congruence equation of the form x^n = a Mod (b) and the integer solutions for equations like a x^n + by = c. Key methods outlined include prime factorization of b, the application of the Shanks-Tonelli algorithm for finding n-th roots, Hensel lifting for roots modulo p^2, and the use of the Chinese Remainder Theorem to combine solutions. The tools mentioned for implementation include Magma for computational assistance.

PREREQUISITES
  • Understanding of modular arithmetic and congruences
  • Familiarity with prime factorization techniques
  • Knowledge of the Shanks-Tonelli algorithm for square roots
  • Experience with Hensel lifting and the Chinese Remainder Theorem
NEXT STEPS
  • Research the Shanks-Tonelli algorithm for arbitrary roots
  • Study Hensel lifting in detail for polynomial equations
  • Explore the Chinese Remainder Theorem applications in number theory
  • Learn how to implement solutions in Magma for computational verification
USEFUL FOR

Mathematicians, computer scientists, and students studying number theory or cryptography who are interested in solving congruences and integer equations.

eljose
Messages
484
Reaction score
0
:smile: :confused: :cool: :rolleyes: Can anyone help me to provide a solution to the general congruence:

[tex]x^n =a Mod (b)[/tex] a,n and b integers or the integer solution to

equations of the form:

[tex]a x^n + by= c[/tex] solutions for integer x and y
 
Physics news on Phys.org
what prior knowledge was given in the course? Roots? or Powers n^x=amodb? P
 
Plug it into Magma. :smile:


I would do it as follows.

(1) First, find the prime factorization of b. Let's assume b = p^2 * q

(2) Find the n-th root of a modulo p and modulo q. (I know the Shanks-Tonelli algorithm works for square roots, and can be adapted for arbitrary roots. There may be a better way)

(3) Use Hensel lifting to find an n-th root of a modulo p^2

(4) Use the Chinese Remainder Theorem to find an n-th root of a modulo b
 

Similar threads

Undergrad Question on Primitive Roots and GCDs
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
6K
Undergrad Meaning of terms in a direct sum decomposition of an algebra
  • · Replies 8 ·
Replies
8
Views
3K
Undergrad Congruence for Symmetric and non-Symmetric Matrices for Quadratic Form
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Dimension and solution to matrix-vector product
  • · Replies 4 ·
Replies
4
Views
3K
Graduate Residues and non residues of general quadratic congruences
  • · Replies 1 ·
Replies
1
Views
2K
MHB Can All Linear Diophantine Equations Be Solved?
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Existence and Uniqueness of Inverses
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Can one find a matrix that's 'unique' to a collection of eigenvectors?
  • · Replies 33 ·
2
Replies
33
Views
3K
MHB About a variant of the Chinese Remainder Theorem
  • · Replies 5 ·
Replies
5
Views
2K