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

Does this have any meaning:x = (-6) mod 5Is it just like:x = -(6

  1. Jun 1, 2004 #1
    Does this have any meaning:
    x = (-6) mod 5
    Is it just like:
    x = -(6 mod 5)
    Or what about:
    x = 6 mod (-5)
    And:
    x = 6 mod (5/2)
     
  2. jcsd
  3. Jun 1, 2004 #2
    1.yes
    2. dont think so.
    3.x=6 mod(-5) is like 6=x mod(5)

    btw in the quote i put numbers near your questions.
     
  4. Jun 1, 2004 #3
    What's the result then of (-6) mod 5 and why is it different than -(6 mod 5)? And what about mod (5/2)?

    Thanks,
     
  5. Jun 1, 2004 #4
    x = -6 (mod 5) is equivalent to x + 6 = 0 (mod 5), or x + 1 = 0 (mod 5). It's obviously not uniquely determined, but the smallest positive x that'll work is x = 4.

    Personally, I'd say that -(6 (mod 5)) = -(1) = -1, which is not 4 ;) But I don't know, I've never seen an expression like that.

    And about x = 6 mod (5/2), it's the same as saying x - 6 = 0 (mod 5/2), or x - 6 is divisible by 5/2. How do you propose we define "divisibility" in the rational numbers...? Seems like nonsense to me :)
     
    Last edited: Jun 1, 2004
  6. Jun 1, 2004 #5

    jcsd

    User Avatar
    Science Advisor
    Gold Member

    a ≡ b(mod n) can be extended to include cases where a and b are real numbers, for example: 5.74 ≡ -3.26(mod 3), but n must be a natural number.
     
    Last edited: Jun 1, 2004
  7. Jun 1, 2004 #6
    muzza got to you first in the post. (:
    btw chen i see a pattern in your posts (perhaps is just my imagination) have you recently read the book of simon singh called: "secrets of encryption (or is it decryption)" because in this book theere's a brief overview of modulus and quantum cryptography.

    anyway if you havent read the book you should, it's a great book.
     
  8. Jun 1, 2004 #7
    I read The Code Book (that the original name, it got changed in the translation to Hebrew) not so recently - last summer. But I've applied to the Technyon's excellence program and the next step is to prepare a lecture about a scientific subject of some sort... so I chose quantum cryptography, but in the process I also talk about classical cryptography (RSA, Diffie-Helllman) so I want to make sure I understand everything. :smile: Unfortunately I don't have the book right now, it was my friend's, so I'm trying to recollect what I read. If you want I can send you the paper once I'm done...

    Good guess, by the way... :biggrin:
     
    Last edited: Jun 1, 2004
  9. Jun 1, 2004 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    4 is congruent to -1 is congruent to - 6 mod 5, they are all the same mod 5.

    remeber that when you write 1 in mod five you actually mean the equivlance class [1], so that [4]=[-1]=[-6], note that -[r]=[-r].

    You should not extend modulo arithemetic without care beyond the integers, otherwise you WILL hit problems, particularly mod a composite: you are implying that 1/3 exists mod 6, and is not zero, but 3 has no multiplicative inverse mod 6
     
  10. Jun 1, 2004 #9
    Alright, thanks. :smile: I was just wondering really how far you can take this action.

    One more thing, how can I prove that xmk mod k = 1 for every x, m and k? I hope it's not too complicated.
     
  11. Jun 1, 2004 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper


    you can't prove it because it's not true. counter example x=k any k. if we force x to be non-zero then x=2, k=4, m=anything.

    what is true is if k is a prime then x^k=x mod k for all x, or if you prefer x^{k-1}=1 mod k for all non-zero x k a prime - fermat's little theorem.

    more generally, if x and k are coprime then x^{\phi(k)}=1 mod k, where phi is euler's totient function. the proofs are in any elementary number theory/group theory book.
     
  12. Jun 1, 2004 #11
    Hmm, that's right. I tried to simplify the problem but I made a mistake along the way. I'll look for the complete proof somewhere else, I imagine it's long.
     
  13. Jun 1, 2004 #12

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Look up some book on elementary number theory. Should cover congruences pretty early

    P.S : I've read the Code Book too - in fact, I have it. Was quite fun. There's another book I have at home that goes through the math needed to understand how RSA works. I'll tell you what it's called when I get home. You should be able to find it in a library.
     
    Last edited: Jun 1, 2004
  14. Jun 1, 2004 #13
  15. Jun 1, 2004 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    given the k of mod k, the elements prime to it of 1,2,...,k-1 form a group of rder \phi(k), so fermat's (extended) little theorem follows from lagrange's theorem for groups (for any finite group, the order of the element divides the order of the group). that they form a group (under multiplication obviously) follows constructively from the euclidean algorithm which constructs explicitly the x and y needed in gcd(a,b)=ax+by in your above post
     
  16. Jun 2, 2004 #15

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    "The Mathematics of Ciphers - Number Theory and RSA Cryptography" by S.C. Coutinho
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Does this have any meaning:x = (-6) mod 5Is it just like:x = -(6
Loading...