抖阴探探

Modular arithmetic and Euclid鈥檚 algorithm

Author

Clayton Cafiero

Published

2025-01-05

Here鈥檚 a video (10:13) that gives a brief introduction to modular arithmetic. Modular arithmetic is useful in many applications, including

Note that % in C++ isn鈥檛 strictly the modulus operator it is the 鈥渞emainder after division鈥� operator. So you may get answers that are a little surprising when working with integers. For example, in C++ there鈥檚 a difference between 3 / 2 (where both operands are integers) and 3.0 / 2.0 (where operands are floats). (If you鈥檝e seen the // integer division operator in Python, this might ring a bell.) So,

Sometimes things behave as expected, for example, in C++, 17 % 7 == 3, but 17 % -5 == 2, and -4 % 1 == 0. Wait! What?

Don鈥檛 panic. Here鈥檚 a formula that will always give you the correct answer in C++: (a / b) * b + (a % b) == a.

Remember: a / b here is integer division, so (a / b) * b isn鈥檛 always a. Here are examples for finding the remainder of integer division for the examples given above. First, let鈥檚 rearrange terms so that we have (a % b) on the right hand side: a - (a / b) * b == a % b.

So, 17 - (17 / -5) * -5 == 17 % -5. Now, 17 / -5 == -3, and `-3 * -5 == 15, so we have 17 - 15 == 2, and thus 17 % -5 == 2.

Next, let鈥檚 do -4 % 1.

-4 - (-4 / 1) * 1 == -4 % 1. Now, 4 / -1 == -4, and -4 * 1 == -4, therefore we have -4 - (-4) == 0, and thus -4 % 1 == 0.

See: Essential Algorithms, pp. 33鈥�34 for more on Euclid鈥檚 algorithm.

Further reading

  • (Wikipedia)

Comprehension check

  1. What is 27 \pmod 8?
  2. What is 27 + 3 \pmod {11}?
  3. In C++, what is 14 % 5?
  4. In C++, what is 14 % -5?
  5. In C++, what is 7 % 0?

Answers: p菨u岽壣熐漰un / 晒no蔁 / 晒no蔁 / 蕠丧苾岽壡� / 菨菨晒丧蕠

Copyright 漏 2023鈥�2025 Clayton Cafiero

No generative AI was used in producing this material. This was written the old-fashioned way.

Reuse