1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Solving nonlinear congruences

  1. Dec 12, 2011 #1
    1. The problem statement, all variables and given/known data

    Find an integer x that is a solution (only need one solution, not all solutions). If no solution exists, prove that no solution can exist.

    13x = 13 mod 50032 , with x > 1. Note that 5003 is prime.

    Here, = means "congruent to"

    2. Relevant equations

    Not sure. I can solve linear congruences without too much trouble, but I haven't seen a congruence of this form before, and the book that I'm using is pretty low on good examples.

    3. The attempt at a solution

    I don't have one. Looking for a bump in the right direction.
  2. jcsd
  3. Dec 13, 2011 #2
    I spent a lot of time last night trying a bunch of different techniques on your problem and couldn't get much of anywhere. But since no one else has responded to it yet I will give you what little I have, which is just Fermat's Little Theorem:

    13^5003 = 13 mod 5003. But from here I don't know where to go.
  4. Dec 13, 2011 #3
  5. Dec 13, 2011 #4
    I can use Euler's theorem since 13 and 50032 are coprime.

    However, I then end up with: 13phi(50032) = 1 mod 50032. How can I manipulate this so that I have 13 mod 50032 instead of 1 mod 50032?
  6. Dec 13, 2011 #5
    Can't you just multiply both sides by 13?
  7. Dec 13, 2011 #6
    Sigh .... yes. Yes I can. I think it's time for a break, I've been staring at this for too long and I'm starting to forget about basic math.

    Thanks for the wake up call!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook