Confusing step in modular arithmetic proof [closed]

by

I’m trying to understand the steps in this proof that are boxed in yellow.

Suppose x = c is a solution to ax = b (mod M), which means (ac) mod M = b mod M. We want to prove that y = c mod M is also a solution.

The author multiplies both sides of y = c mod M by a, resulting in ay = a(c mod M). What I don’t understand is how the author claims the right-hand side becomes b mod M “since c is a solution”. Paying close attention to parentheses, I can see how (ac) mod M = b mod M, but this does not imply that a*(c mod M) = b mod M. I am confused by how an integer can be moved inside the modulo operator, since (ac) mod M != a*(c mod M). Am I missing something here? Proof

I can see how (ac) mod M = b mod M, but this does not imply that a*(c mod M) = b mod M. I am confused by how an integer can be moved inside the modulo operator, since (ac) mod M != a*(c mod M)

  • 1

    Welcome to Stack Overflow. Please take the tour to learn how Stack Overflow works and read How to Ask on how to improve the quality of your question. Then check the help center to see which questions are on-topic on this site. You might want to delete this question and ask it on math.stackexchange.com instead, but check the help pages there first.

    – 

  • In computer programming, mod is a binary operator. In mathematics, mod is a special type of equality, not an operator. In mathematics, a(c mod M) makes no sense. The mod M applies to the = symbol., not to the c.

    – 




  • How does a(c mod M) make no sense? a = 2 c = 2 M = 3 a (c mod M) = 2*(2 mod 3) = 2*2 = 4 Seems perfectly reasonable to me, regardless of whether we are talking about computer programming or “mathematics”.

    – 




  • In programming “2 mod 3” is 2. In mathematics, “2 mod 3” is not a thing. Rather “a = b (mod n)” means that “a = b + k*n” for some integer k. The operator is = (mod n)”, but the “mod n” part is written at the end rather than next to the = sign.

    – 




  • Thanks. So referring to the proof link in the original question, are you suggesting that the author is abusing notation when writing something like y = c mod M? Would it be more clear if the mod M was in parentheses, like y = c (mod M) ?

    – 

Leave a Comment