Can Nonlinear Congruences Be Solved? A Case Study with a Prime Modulus

[joshuathefrog]

Homework Statement

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.

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

Here, = means "congruent to"

Homework 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.

The Attempt at a Solution

I don't have one. Looking for a bump in the right direction.

 

[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.

 

[micromass]

You could use Euler's theorem: http://en.wikipedia.org/wiki/Euler's_theorem

 

[joshuathefrog]

I can use Euler's theorem since 13 and 5003² are coprime.

However, I then end up with: 13^phi(50032) = 1 mod 5003². How can I manipulate this so that I have 13 mod 5003² instead of 1 mod 5003²?

 

[Poopsilon]

Can't you just multiply both sides by 13?

 

[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!