# Solving x^{n}+a=mod(b) (1 Viewer)

### Users Who Are Viewing This Thread (Users: 0, Guests: 1)

#### lokofer

If a,b,n are integers..how could you solve:

$$x^{n}+a=mod(b)$$ n>0 and integer..

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

$$ax=bmod(c)$$ but i don't know how to solve "upper" congruences..thanks.

#### CRGreathouse

Homework Helper
I really don't know what you're asking. I presume the question you've already solved is $$ax\equiv b\pmod c$$ but I'm not sure what your first is. Depending on what you mean, you might be able to use reciprocity.

Last edited:

#### lokofer

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?..

#### matt grime

Homework Helper
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.

#### lokofer

- I don't know why is the "congruence" $$x^{n}=amod(b)$$ for n>1 in fact it's nothing but a Monomial..you could calculate all the roots of $$x^{n}-a=0$$ easily and from this find a solution...  #### matt grime

Homework Helper
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.

#### HallsofIvy

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?

#### lokofer

-For example "Hallfosftivy"..a solution to the (general ) congruence:

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

$$[\frac{f(x)-a}{x}]-\frac{f(x)-a}{x}=0$$ or 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...

#### matt grime

Homework Helper
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).

### The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving