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

Homework Help: 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]
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook