The Integers Modulo m

Two integers a and b are congruent modulo m if and only if a - b is a multiple of m, in which case we write a≡b $\left(\vphantom{ \limfunc{mod}m}\right.$$\limfunc$modm$\left.\vphantom{ \limfunc{mod}m}\right)$. Thus, 15≡33 $\left(\vphantom{ \limfunc{mod}9}\right.$$\limfunc$mod9$\left.\vphantom{ \limfunc{mod}9}\right)$, because 15 - 33 =   - 18 is a multiple of 9. Given integers a and m, the mod function is given by a$\limfunc$modm = b if and only if a≡b $\left(\vphantom{ \limfunc{mod}m}\right.$$\limfunc$modm$\left.\vphantom{ \limfunc{mod}m}\right)$ and 0≤b≤m - 1; hence, a$\limfunc$modm is the smallest nonnegative residue of a modulo m.

The underlying computer algebra system does not understand the congruence notation a≡b$\left(\vphantom{ \limfunc{mod}m}\right.$$\limfunc$modm$\left.\vphantom{ \limfunc{mod}m}\right)$, but it does understand the function notation a$\limfunc$modm. This section shows how to translate problems in algebra and number theory into language that Scientific Notebook can handle.

Note that $\limfunc$mod is a function of two variables, with the function written between the two variables. This usage is similar to the common usage of +, which is also a function of two variables with the function values expressed as a + b, rather than the usual functional notation + (a, b).

Traditionally the congruence notation a≡b $\left(\vphantom{ \limfunc{mod}% m}\right.$$\limfunc$modm$\left.\vphantom{ \limfunc{mod}% m}\right)$ is written with the $\func$modm enclosed inside parentheses since the $\func$modm clarifies the expression a≡b. In this context, the expression b $\left(\vphantom{ \limfunc{mod}m}\right.$$\limfunc$modm$\left.\vphantom{ \limfunc{mod}m}\right)$ never appears without the preceding a≡. On the other hand, the $\func$mod function is usually written in the form a$\func$modm without parentheses.


$\blacktriangleright$ To evaluate the mod function

1.
Leave the insertion point in the expression a$\limfunc$modb.

2.
Choose Evaluate.


$\blacktriangleright$ Evaluate

23$\limfunc$mod14 = 9


If a is positive, you can also find the smallest nonnegative residue of a modulo m by applying Expand to the quotient ${\frac{{a}}{{m}}}$.

$\blacktriangleright$ Expand

${\dfrac{{23}}{{14}}}$ = 1${\dfrac{{9}}{{14}}}$

Since 1${\frac{{9}}{{14}}}$ = 1 + ${\frac{{9}}{{14}}}$, multiplication of ${\frac{{23}}{{14}}}$ = 1 + ${\frac{{9}}{{14}}}$ by 14 shows that 23$\limfunc$mod14 = 9.

In terms of the floorDM2-4.tex#Floor function $\left\lfloor\vphantom{ x}\right.$x$\left.\vphantom{ x}\right\rfloor$, the mod function is given by a$\func$modm = a - $\left\lfloor\vphantom{ \frac{a}{m}}\right.$${\frac{{a}}{{m}}}$$\left.\vphantom{ \frac{a}{m}}\right\rfloor$m .


$\blacktriangleright$ Evaluate

23 - $\left\lfloor\vphantom{ \frac{23}{14}}\right.$${\frac{{23}}{{14}}}$$\left.\vphantom{ \frac{23}{14}}\right\rfloor$14 = 9


Subsections