Solving Upper Congruences: Step-by-Step Guide for x^{n}+a=mod(b)

  • Thread starter lokofer
  • Start date
In summary: There are no "approximations" to integers- a solution to a (general) congruence is a solution to the equation in the form: [\frac{f(x)-a}{x}]-\frac{f(x)-a}{x}=0. If we define the function: <x>=x-[x] where "[x] " is the floor function then: <\frac{f(x)-a}{x}>=0 so from this you could calculate all the "roots" (integers) and solution to the initial congruence.
  • #1
lokofer
106
0
If a,b,n are integers..how could you solve:

[tex] x^{n}+a=mod(b) [/tex] n>0 and integer..

If possible please put an "step by step" example..i have managed to solve the linear congruence

[tex] ax=bmod(c) [/tex] but i don't know how to solve "upper" congruences..thanks.
 
Physics news on Phys.org
  • #2
I really don't know what you're asking. I presume the question you've already solved is [tex]ax\equiv b\pmod c[/tex] but I'm not sure what your first is. Depending on what you mean, you might be able to use reciprocity.
 
Last edited:
  • #3
i know how to solve for n=1 then i would like to know how to solve the special case y proposed...

- By the way...are not there "approximate" or numerical method to calculate the set of the solutions?..
 
  • #4
If you can solve for any x other than 1 (or 2) easily then you've just proven RSA easy to break. Come on, Jose, think for a second before posting a question: taking roots mod c is hard, and that's the whole point of RSA.
 
  • #5
- I don't know why is the "congruence" [tex] x^{n}=amod(b) [/tex] for n>1 in fact it's nothing but a Monomial..you could calculate all the roots of [tex] x^{n}-a=0 [/tex] easily and from this find a solution... :rolleyes: :rolleyes:
 
  • #6
Then why don't you 'just do it'? You really ought to get straight in your mind what a function is, what an algorithm to find a value of said function is, and what you consider to be a reasonable cost for carrying out the algorithm, and then state what that is.
 
  • #7
lokofer said:
i know how to solve for n=1 then i would like to know how to solve the special case y proposed...

- By the way...are not there "approximate" or numerical method to calculate the set of the solutions?..
What would be an "approximation" to an integer?
 
  • #8
-For example "Hallfosftivy"..a solution to the (general ) congruence:

[tex] f(x)=amod(x) [/tex] (for example) is the solution to the "equation" (non-linear) in the form:

[tex] [\frac{f(x)-a}{x}]-\frac{f(x)-a}{x}=0 [/tex] or if we define the function:

[tex] <x>=x-[x] [/tex] where "[x] " is the floor function then:

[tex] <\frac{f(x)-a}{x}>=0 [/tex] so from this you could calculate all the "roots" (integers) and solution to the initial congruence...
 
  • #9
Go on then. Do it. Show that it's better than a simple exhastive search through phi(c) options, (or c-1 if you don't know the factorization of c).
 

1. What is an upper congruence?

An upper congruence is a mathematical equation in the form of x^n + a = mod(b), where x is the unknown variable, n is a positive integer, a is a constant, and b is the modulus. This equation is used to find values of x that satisfy the congruence.

2. How do you solve an upper congruence?

To solve an upper congruence, you need to use a step-by-step approach. First, you need to isolate x^n by subtracting a from both sides of the equation. Then, take the nth root of both sides. Next, use modular arithmetic to simplify the equation by dividing both sides by the modulus. Finally, solve for x by using the inverse of the modulus.

3. What is the purpose of solving upper congruences?

Solving upper congruences is used in many fields of mathematics, such as number theory, cryptography, and computer science. It allows us to find solutions to equations involving modular arithmetic, which is essential in many real-world applications.

4. Can you provide an example of solving an upper congruence?

Sure, let's say we have the congruence x^2 + 2 = mod(7). We would first isolate x^2 by subtracting 2 from both sides, giving us x^2 = mod(5). Then, we would take the square root of both sides, giving us x = mod(5). Using modular arithmetic, we can simplify this to x = 3 (since 5 mod 7 is equivalent to 3). Therefore, the solution to this congruence is x = 3.

5. Are there any special cases when solving upper congruences?

Yes, when the exponent, n, is an even number, there may be multiple solutions to the congruence. This is because taking the nth root can result in both a positive and negative solution. In these cases, it is important to check both solutions to ensure they satisfy the congruence.

Similar threads

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
864
I Want to understand how to express the derivative as a matrix
    • Linear and Abstract Algebra
Replies
8
Views
1K
Number of quadratic residues mod N>1
    • Linear and Abstract Algebra
Replies
4
Views
3K
If n = x(mod 10x+1) n,x>0
    • Linear and Abstract Algebra
Replies
1
Views
3K
Prove ## a/d\equiv b/d \mod n/d ##.
    • Precalculus Mathematics Homework Help
Replies
2
Views
687
Residues and non residues of general quadratic congruences
    • Linear and Abstract Algebra
Replies
1
Views
2K
I Meaning of terms in a direct sum decomposition of an algebra
    • Linear and Abstract Algebra
Replies
8
Views
2K
MHB Solving Congruences with Polynomials: A Prime Challenge
    • Linear and Abstract Algebra
Replies
5
Views
3K
MHB Exploring Finite Group Theory: Finding the Upper Bound of Groups of Order
    • Linear and Abstract Algebra
Replies
2
Views
973

Hot Threads

Recent Insights

Back
Top