solution to the general congruence

eljose

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

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