Solution to the general congruence

[eljose]

Can anyone help me to provide a solution to the general congruence:

$$x^n =a Mod (b)$$ a,n and b integers or the integer solution to

equations of the form:

$$a x^n + by= c$$ solutions for integer x and y

 

[neurocomp2003]

what prior knowledge was given in the course? Roots? or Powers n^x=amodb? P

 

[Hurkyl]

Plug it into Magma.


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