1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Rules of Modular Arithmetic

  1. Oct 4, 2005 #1
    Is it possible to manipulate and substitute modulos like so

    a^5 = a (mod 5)
    a^3 = a (mod 3)

    a^15 = a (mod 15)

    By substituting the first into the second?
     
  2. jcsd
  3. Oct 4, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It helps to fall back on the definitions...

    Recall that a^5 = a (mod 5) means 5 | (a^5 - a).
    Similarly, a^3 = a (mod 3) means 3 | (a^3 - a).

    Now that the problem's converted into ordinary arithmetic, can you figure anything out?
     
  4. Oct 5, 2005 #3
    so 15 | (a^5 - a)(a^3 - a)
    or 15 | a^8 - a^6 - a^4 + a^2

    is that what you mean, Hurkyl?
     
  5. Oct 5, 2005 #4
    a^p (mod n) as a increases or as p increases is cyclic, is it not? I think I can answer my question using this property.
     
  6. Oct 5, 2005 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yep.

    Huh? I'm not sure if you're getting there or not...
     
  7. Oct 5, 2005 #6
    Mmm, I thought I needed this property to prove another theorem, but it seems I was wrong. I'll try to do it anyway though:

    5n = a^5-a
    3k = a^3-a

    5n-3k = a^5-a^3 = a^2(a^3-a)

    I'll try to finish later.
     
  8. Oct 5, 2005 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Here's another way of looking at it: if a^15 = a (mod 15), then you have a = a^15 = (a^3)^5 = a^5 (mod 3). Do you think a = a^5 (mod 3)?

    Now you do have this nifty theorem:

    If m and n are relatively prime, then:

    [tex]
    m^{\phi(n)} = 1 \mod n
    [/tex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Rules of Modular Arithmetic
  1. Modular arithmetic (Replies: 3)

  2. Modular arithmetic (Replies: 3)

  3. Modular arithmetic (Replies: 6)

  4. Modular Arithmetic (Replies: 23)

  5. Modular arithmetic (Replies: 3)

Loading...