1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Simple but annoying characteristic of congruences

  1. Feb 25, 2013 #1
    I've been having this small problem with modulo arithmetic that's just irking me and this is the perfect example to get clarifivation

    find the remainder for 75 congruent to x (mod 21)

    here's my issue....so I'd set this up to solve and see if I could find this relationship

    7[itex]\equiv[/itex] x (mod 21)........now 7 is a multiple of 21, but of course 21 doesn't divide 7 unless we take into account the negative numbers which would produce 7 [itex]\equiv[/itex] -12 (mod 21)...........is this the right way to look at that?

    the next thing I did and which made it easier was look at 72 [itex]\equiv[/itex] 7 (mod 21) .....now I have 75 [itex]\equiv[/itex] 7 (mod 21) when all is said and done....but the fact that I know 7 has a relationship with 21 is sitting uneasy with me...
    Last edited: Feb 25, 2013
  2. jcsd
  3. Feb 25, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper

    Don't know what's sitting uneasy with you. Sure, if 7^2=7 (mod 21) then 7^5=7 (mod 21).
  4. Feb 25, 2013 #3

    Well it has to do with an RSA encoding question, in order to encode my message which in this case is 7, I have to send the remainder when I raise 7 to the power of 5.........which ended up being 7. Probably I'm just over thinking it
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted