Solving nonlinear congruences

1. Dec 12, 2011

joshuathefrog

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. Dec 13, 2011

Poopsilon

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.

3. Dec 13, 2011

micromass

Staff Emeritus
4. Dec 13, 2011

joshuathefrog

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?

5. Dec 13, 2011

Poopsilon

Can't you just multiply both sides by 13?

6. Dec 13, 2011

joshuathefrog

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!