Wikipedia:Reference desk/Archives/Mathematics/2020 August 12

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 12

Modular Arithmetic

How can I calculate modular subtraction if a is greater than b.

${\bar {b}}-{\bar {a}}$

— Preceding unsigned comment added by 185.181.55.124 (talk) 11:04, 12 August 2020 (UTC)

Courtesy link: Modular arithmetic -- ToE 12:53, 12 August 2020 (UTC)

For modulus n, if your difference is negative, then add as many multiples of n as is necessary to make it nonnegative. Specifically, if 0 ≤ b < a < n, then the addition of a single copy of n suffices:

(b - a) mod n = b - a + n

This is similar to how with addition you subtract an n if a + b ≥ n.

-- ToE 12:53, 12 August 2020 (UTC) Edit: Restated in terms of Modulo operator. -- ToE 13:11, 12 August 2020 (UTC) Edited again to correct order in inequality. Thanks Lambiam. -- ToE 15:31, 12 August 2020 (UTC)

Strictly speaking, the equality ${\overline {b}}-{\overline {a}}={\overline {b-a}}$ holds in modular arithmetic, also when $a$ is greater than $b$. But that is apparently not the answer you are looking for; you want a solution to the equation ${\overline {b}}-{\overline {a}}={\overline {x}}$ in which the right-hand side is normalized, that is, such that $0\leq x<n$. Recalling the definition of the congruence class denoted by ${\overline {b-a}}$, we see that it is the set

$\{...,~(b-a)-2n,~(b-a)-n,~(b-a),~(b-a)+n,~(b-a)+2n,~...\}~,$

so that the question now is: which of these infinitely many elements lies in the range from $0$ to $n{-}1$? (I am assuming here that the modulus $n>0$.) Each element of this set is of the form $(b-a)+kn$, in which $k$ is an integer. So to find $x=(b-a)+kn$ subject to the constraint that $0\leq x<n$, we need to find $k$ satisfying $0\leq (b-a)+kn<n$, or, equivalently,

${\frac {a-b}{n}}\leq k<{\frac {n+a-b}{n}}.$

There is only one integer satisfying both inequations, and if some $k$ does, then $k{+}1$ will also satisfy the left inequation and therefore fail the other one. This means that $k$ is the least integer satisfying ${\frac {a-b}{n}}\leq k$, and so is given by $k=\lceil {\tfrac {a-b}{n}}\rceil$, in which $\lceil \cdot \rceil$ denotes the ceiling function. This is of course equivalent to the much simpler answer provided in the first response, but gives an explicit formule for the general case, together with the mathematical reasoning behind it.  --Lambiam 15:06, 12 August 2020 (UTC)

There is a lot of confusion between congruence classes and the remainder function, exacerbated by the fact that computer notation often uses 'mod' to denote the remainder. This can have the effect of making modular arithmetic seem difficult. But actually people do modular arithmetic (addition and subtraction at least) without thinking about it when dealing with time. I assume most people can figure out how many hours it is from 10 o'clock to 2 o'clock without thinking about equivalence classes and residue systems; see the lead section of the article on modular arithmetic. --RDBury (talk) 21:48, 12 August 2020 (UTC)