# Solution to the general congruence

1. Aug 6, 2006

### eljose

:rofl: 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 :grumpy: :grumpy:

2. Aug 6, 2006

### neurocomp2003

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

3. Aug 6, 2006

### Hurkyl

Staff Emeritus
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