Solution to the general congruence

  • Thread starter eljose
  • Start date
  • Tags
    General
In summary, the conversation discusses finding solutions for equations of the form ax^n + by = c, where a, n, and b are integers. The suggested method involves finding the prime factorization of b, using the Shanks-Tonelli algorithm to find n-th roots modulo prime factors, and then using Hensel lifting and the Chinese Remainder Theorem to find a solution modulo b. No prior knowledge was mentioned, but it is recommended to have some understanding of roots and powers, and to use Magma for calculations.
  • #1
eljose
492
0
:rofl: :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 :grumpy: :grumpy:
 
Physics news on Phys.org
  • #2
what prior knowledge was given in the course? Roots? or Powers n^x=amodb? P
 
  • #3
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
 

What is a solution to the general congruence?

A solution to the general congruence is a value that satisfies the congruence equation, which is of the form a ≡ b (mod n). In other words, the solution is a number that, when divided by n, leaves a remainder of b.

How do you find a solution to the general congruence?

To find a solution to the general congruence, you can use the extended Euclidean algorithm or modular arithmetic. These methods involve manipulating the congruence equation to solve for the unknown variable.

Are there always solutions to the general congruence?

Yes, there are always solutions to the general congruence as long as the numbers involved are integers. In some cases, there may be multiple solutions.

How do you know if a solution to the general congruence is unique?

A solution to the general congruence is unique if the greatest common divisor of the two numbers a and n is 1. This means that there are no other numbers that can evenly divide both a and n, resulting in a unique solution.

What is the importance of the general congruence in mathematics?

The general congruence is important in number theory, cryptography, and other branches of mathematics. It allows for the study of patterns and relationships between numbers, and has applications in encryption and data security.

Similar threads

I Question on Primitive Roots and GCDs
    • Linear and Abstract Algebra
Replies
2
Views
787
I Dimension and solution to matrix-vector product
    • Linear and Abstract Algebra
Replies
4
Views
868
I Meaning of terms in a direct sum decomposition of an algebra
    • Linear and Abstract Algebra
Replies
8
Views
2K
I Congruence for Symmetric and non-Symmetric Matrices for Quadratic Form
    • Linear and Abstract Algebra
Replies
7
Views
827
I Existence and Uniqueness of Inverses
    • Linear and Abstract Algebra
Replies
5
Views
865
Prove that the congruences admit a simultaneous solution
    • Precalculus Mathematics Homework Help
Replies
5
Views
924
I Diophantine approximation via Lattice Reduction
    • Linear and Abstract Algebra
Replies
1
Views
635
I Want to understand how to express the derivative as a matrix
    • Linear and Abstract Algebra
Replies
8
Views
1K
[IntroNumTheory] Determining the remainder by using congruence
    • Calculus and Beyond Homework Help
Replies
1
Views
711
I Finding a polynomial that has solution (root) as the sum of roots
    • Linear and Abstract Algebra
Replies
13
Views
1K

Hot Threads

Recent Insights

Back
Top