Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solution to the general congruence

  1. Aug 6, 2006 #1
    :rofl: :confused: :cool: :rolleyes: 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 :grumpy: :grumpy:
  2. jcsd
  3. Aug 6, 2006 #2
    what prior knowledge was given in the course? Roots? or Powers n^x=amodb? P
  4. Aug 6, 2006 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Plug it into Magma. :smile:

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook