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

Mods that will rack your brain

  1. Jul 3, 2004 #1
    show that a^13 is congruent to a (modulo 2730)

    if a is an integer such that a is not divisidble by 3, or such that a IS divisible by 9, then a^7 is congruent to a (mod 63)

    with these, could i just divide the mod numbers by the powers? that is what i am doing, but it seems like as though it ISN'T right... anyone help ?
     
  2. jcsd
  3. Jul 4, 2004 #2

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Have you come across Fermat's Little Theorem ?

    a^p == a (mod p) for prime p
     
  4. Jul 4, 2004 #3
    gokul, could i say that b/c of fermat's thm, i can say that it IS == to a, because of the fact that 13 is prime? would i need to prove any further? also, could that work for the second one? anyone else think so?
     
  5. Jul 4, 2004 #4

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    What exactly are you asking? According to that theorem

    a^13 = a (mod 13), but you need to show a^13 = a (mod 2730), so of course you need to prove more! I've never taken any courses on number theory, but you might know a theorem that takes advantage of the fact that 2730 = 0 (mod 13).
     
  6. Jul 4, 2004 #5
    ok so i could set it up, then say, "according to fermat's theorem,... and apply the theorem to this probloem?
     
  7. Jul 4, 2004 #6

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Uhh.. are you asking if you're allowed to use Fermat's Little Theorem? I suppose you should ask your teacher/prof/t.a.
     
  8. Jul 4, 2004 #7

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I haven't taken any courses either...but this is what I would do. The folks that really know some number theory probably have a far better approach.

    2730 = 13*7*5*3*2
    So we are done if we can show that a^13 == a (mod n), for n=2,3,5,7, and 13.
    Use both forms of the Little Theorem...
    a^p == a (mod p), for all prime p and a^(p-1) == 1 (mod p) for prime p, when p does not divide a.

    Clearly a^13 == a (mod 13) ---- (1)

    Also a^7 == a (mod 7) and
    a^6 == 1 (mod 7), so
    (a^7)*(a^6) = a^13 == a*1 (mod 7) ---(2)

    Again, a^5 == a (mod 5)
    and a^4 == 1 (mod 5) => a^8 == 1 (mod 5)
    Hence a^13 == a (mod 5) ---(3)

    Likewise, show this for n=3 and n=2..and you are done.

    This proof lacks some rigor (in that, for each result, the exceptions need to be covered. This is not hard at all), but I'm going to leave that to you to find and fill in.
     
    Last edited: Jul 5, 2004
  9. Jul 4, 2004 #8

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Gokul43201

    I don't know why it's sufficient to show that [itex]a^{13} \equiv a\ (\mbox{mod }n)[/itex] for those n, but unless a = 1 or a = 0, a cannot be congruent to a (mod 2).

    1+1=1

    For your second question, part of it is easy:

    To prove [itex]a^7 \equiv a\ (\mbox{mod }63)[/itex] if a is divisible by 9, we can start by saying:

    [tex]a^7 \equiv a\ (\mbox{mod }7)[/tex]

    Therefore, for some integer x:

    [tex]a^7 = 7x + a[/tex]

    Now, since a is a multiple of 9, [itex]a^7[/itex] must also be a multiple of 9, and thus 7x must also be a multiple of 9. So, for some integer y, x = 9y. Now, we have:

    [tex]a^7 = 63y + a[/tex]

    I think this is sufficient to prove [itex]a^7 \equiv a\ (\mbox{mod }63)[/itex] if a is divisible by 9.
     
    Last edited: Jul 4, 2004
  10. Jul 4, 2004 #9
    No dividing by 0

    Much of the work on the problem is good, but remember that we can not divide by 0. For that reason forget about a^p ==a implies a^(p-1) ==1. That is not true in general. For example in the case of a^13 = =a Mod 7, we have a^13 =a^7 x a^6 ==a x a^6 == a^7 ==a Mod 7, this is true even for a=7. The arithmetic is 7^7 ==7==0 Mod 7, but 7^6 ==0 Mod7 also, not 1.
     
    Last edited: Jul 4, 2004
  11. Jul 4, 2004 #10

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If a==b (mod n) and a==b (mod m), then a==b (mod mn), if gcd(m,n)=1.

    AND

    If n divides a, ie. if a==0 (mod n), then clearly a^k == 0 (mod n), which implies that a^k==a (mod n).

    I think I've said too much already.
     
    Last edited: Jul 5, 2004
  12. Jul 5, 2004 #11

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm not sure if this is directed at me...

    I insist that nothing I have said is wrong, and that I do not carelessly divide congruence relations. Please re-read what I have written.
     
  13. Jul 5, 2004 #12

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Post#10, line 1.

    What ? Any number is always congruent to itself ! Isn't 'congruence' a reflexive relation ? Isn't 0 divisible by all numbers ?

    This looks okay. But there's a shorter way...see post#10.
     
    Last edited: Jul 5, 2004
  14. Jul 5, 2004 #13
    No, it's not true in general, but it IS true when p is prime and p doesn't divide a (i.e a != 0 (mod p)). Besides, Gokul43201 was talking about modulo p, so your counterexample doesn't hold.
     
    Last edited: Jul 5, 2004
  15. Jul 5, 2004 #14
    first of all, thank you to all who helped with the input! i too figured some of it out on my own, but with this it reinforced what i had! isn't that what learning is about, doing some on your own then seeing what others have? i wish i could meet you all and thank yall in person! :biggrin:
     
  16. Jul 5, 2004 #15

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Oh, you're right. I was thinking that a (mod 2) didn't work if a > 2, I thought 17 (mod 4) would be wrong, and 1 (mod 4) would be the right way to do it, but I suppose they're both right, I've just never seen "17 (mod 4)" or "a (mod 2)" [for a > 2] before.
     
  17. Jul 5, 2004 #16
    I thought you said, I took it from what you wrote:

    This what you wrote:
    Also a^7 == a (mod 7) and
    a^6 == 1 (mod 7), so
    (a^7)*(a^6) = a^13 == a*1 (mod 7) ---(2)
     
  18. Jul 5, 2004 #17
    the fact of the problem

    You said, Also a^7 == a (mod 7) and
    a^6 == 1 (mod 7), so
    (a^7)*(a^6) = a^13 == a*1 (mod 7) ---(2)

    Here we really want X^13 ==X Mod 2730, so I thought from how I read you that you were not considering X =7,14,21...etc. That is how I thought about it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Mods that will rack your brain
  1. Mod Problem (Replies: 3)

Loading...