# How to approach this?

1. Oct 11, 2007

### 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?

2. Oct 11, 2007

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

3. Oct 11, 2007

### Werg22

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

4. Oct 11, 2007

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

5. Oct 11, 2007

### Werg22

Thanks allot, I'll see how it develops.

6. Oct 11, 2007

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

Last edited: Oct 11, 2007
7. Oct 12, 2007

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

Last edited: Oct 12, 2007