Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to approach this?

  1. Oct 11, 2007 #1
    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. jcsd
  3. Oct 11, 2007 #2

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Oct 11, 2007 #3
    I admit I am quite shaky with the theory involved, mind giving a bit more details?
     
  5. Oct 11, 2007 #4

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  6. Oct 11, 2007 #5
    Thanks allot, I'll see how it develops.
     
  7. Oct 11, 2007 #6
    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
  8. Oct 12, 2007 #7
    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: How to approach this?
  1. Math approach (Replies: 1)

Loading...