How can I solve [x]^13 + 7*[x] + 5 = 0 in ring 91 efficiently?

[Werg22]

I've got to solve this:

[x]^13 + 7*[x] + 5 = 0 in ring 91.

I've tried solving for [x]^13 and [x] as variables in a Diophante equation but I wasn't able to go anywhere with that. I could try brute force by trying every value for [x] from 0 to 90 but that would just be inconvenient. What should I do?

 

[morphism]

What's ring 91? Do you mean modulo 91? If so, notice that 91=13*7. So to start things off, multiply your equation by 13 to get rid of the [x] term. Then consider things mod 13 and mod 7.

 

[Werg22]

I admit I am quite shaky with the theory involved, mind giving a bit more details?

 

[morphism]

If you multiply by 13, you're going to get
0 = 13[x]^13 + 91[x] + 65 = 13[x]^13 - 26 (mod 91)

If the expression the RHS is divisible by 91, then it's divisible by 7 and 13. Conversely, if it's divisible by both 7 and 13, then it's divisible by 91. But it's clearly divisible by 13, so we really only need to consider 13[x]^13 = 26 (mod 7). Fermat's little theorem can be helpful here.

Generally working modulo a prime is easier than modulo a composite.

 

[Werg22]

Thanks allot, I'll see how it develops.

 

[Werg22]

A quick question why does x^13 = x mod 7? I can't quite pin down the reason; is that a case where Fermat's little theorem comes in hand?

Edit: Nevermind, figured it out.

 

[robert Ihnot]

What you need here is, as mentioned, 91=7*13. Then you can consider the Chinese Remainder Theorem which explains that we can solve this problem for both 7 and 13 and then combine the result. The other matter is Fermat's Little theorem, which says that for prime p, X^p ==x Mod p, that is, X^(p-1)==1 Mod p.

So Mod 13, X^13 ==X. This gives x+7x+5 ==0 Mod 13, or 8x==-5==8 Mod 13. Thus we have X==1 Mod 13. The numbers that solve that are of the form 1+13K = 1, 14, 27,...

You can then proceed in the same manner with the equation Mod 7...