Modulus

[Chen]

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)

[MathematicalPhysicist]

1.Does this have any meaning:
x = (-6) mod 5
2.Is it just like:
x = -(6 mod 5)
3.Or what about:
x = 6 mod (-5)
4.And:
x = 6 mod (5/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.

[Chen]

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,

[Muzza]

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 :)

[jcsd]

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.

[MathematicalPhysicist]

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.

[Chen]

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:

[matt grime]

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

[Chen]

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.

[matt grime]

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.


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.

[Chen]

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.

[Gokul43201]

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.

[Chen]

Actually I found a proof here:
http://cs.colgate.edu/faculty/stina/courses/core/139/s04/notes/rsa-proof.doc
It does skip two steps (gcd(a,b) = xa + yb and Euler's theorem that if m and n are two relatively prime positive integers, then m\phi(n) mod n = 1), but I think I will be able to recover that from somewhere else. :smile:

[matt grime]

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

[Gokul43201]

"The Mathematics of Ciphers - Number Theory and RSA Cryptography" by S.C. Coutinho