Corrected exercises: modular arithmetic (201-N11)

$347=9\times 38+5$, so $347\bmod 9=5$. Check: $9\times 38=342$ and $342+5=347$.

You need a quotient that leaves a remainder in $[0, 7)$: $-38=7\times(-6)+4$, so $-38\bmod 7=4$. Pitfall: $-38=7\times(-5)-3$ gives $-3$, which is not a remainder; add $7$ and you get $4$ back.

$482=8\times 60+2$, $937=8\times 117+1$ and $615=8\times 76+7$. The sum is therefore congruent to $2+1+7=10\equiv 2\pmod 8$. Check: $482+937+615=2{,}034=8\times 254+2$.

$123=11\times 11+2$ and $456=11\times 41+5$, so $123\times 456\equiv 2\times 5=10\pmod{11}$. The remainder is $10$, without ever computing $56{,}088$.

Replace $n$ by its remainder $3$: $3^{3}+2\times 3=27+6=33=4\times 8+1$, so the remainder is $1$, whatever the integer $n\equiv 3\pmod 4$. Check with $n=7$: $343+14=357=4\times 89+1$.

$2{,}999=11\times 272+7$, so $2{,}999^{2}\equiv 7^{2}=49=44+5\equiv 5\pmod{11}$. Pitfall: squaring first, which forces you to divide $8{,}994{,}001$ by $11$.

The cycle: $4^{1}\equiv 4$, $4^{2}=16\equiv 7$, $4^{3}\equiv 4\times 7=28\equiv 1\pmod 9$. Its length is $3$, and $41=3\times 13+2$, so $4^{41}=\left(4^{3}\right)^{13}\times 4^{2}\equiv 1\times 7=7\pmod 9$. Pitfall: reducing the exponent modulo $9$, the modulus, instead of the length of the cycle.

The cycle modulo $10$: $7$, $49\equiv 9$, $9\times 7=63\equiv 3$, $3\times 7=21\equiv 1$, of length $4$. Since $83=4\times 20+3$, $7^{83}\equiv 7^{3}\equiv 3\pmod{10}$: the last digit is $3$.

$13$ is prime and does not divide $2$, so $2^{12}\equiv 1\pmod{13}$. Now $405=12\times 33+9$, so $2^{405}\equiv 2^{9}=512=13\times 39+5\equiv 5\pmod{13}$. Pitfall: reducing the exponent modulo $13$ instead of $13-1=12$, which gives $405\equiv 2$ and a wrong $4$.

$1{,}518=3\times 391+345$; $391=1\times 345+46$; $345=7\times 46+23$; $46=2\times 23+0$. The last nonzero remainder is $23$, so the GCD is $23$. Check: $1{,}518=23\times 66$ and $391=23\times 17$.

$\gcd(5,11)=1$. By trial: $5\times 9=45=44+1\equiv 1\pmod{11}$, so the inverse is $9$. Pitfall: answering $\frac{1}{5}$ or $0.2$; a modular inverse is an INTEGER between $0$ and $10$.

$\gcd(4,15)=1$, and $4\times 4=16=15+1\equiv 1\pmod{15}$: $4$ is its own inverse modulo $15$.

No: $\gcd(9,24)=3\neq 1$. All the multiples of $9$ are multiples of $3$, and so are their remainders modulo $24$, so none of them equals $1$. Pitfall: believing that every nonzero number smaller than the modulus is invertible; that is true only when the modulus is prime.

Euclid: $60=2\times 23+14$; $23=1\times 14+9$; $14=1\times 9+5$; $9=1\times 5+4$; $5=1\times 4+1$. Back substitution: $1=5-4=5-(9-5)=2\times 5-9=2(14-9)-9=2\times 14-3\times 9=2\times 14-3(23-14)=5\times 14-3\times 23=5(60-2\times 23)-3\times 23=5\times 60-13\times 23$. So $-13\times 23\equiv 1\pmod{60}$, and the inverse is $-13+60=47$. Check: $23\times 47=1{,}081=18\times 60+1$. Pitfall: stopping at $-13$, which is not written as a remainder.

Euclid: $75=2\times 32+11$; $32=2\times 11+10$; $11=1\times 10+1$. Back substitution: $1=11-10=11-(32-2\times 11)=3\times 11-32=3(75-2\times 32)-32=3\times 75-7\times 32$. So $u=3$ and $v=-7$, and $u$ does lie between $0$ and $32$. Check: $225-224=1$. Pitfall: expanding every product at each step, which makes you lose track of $75$ and $32$; substitute one division at a time, from the bottom up.

$17$ is prime, so the inverse of $5$ exists: $5\times 7=35=34+1$, it is $7$. Multiply both sides by $7$: $x\equiv 7\times 3=21\equiv 4\pmod{17}$. Check: $5\times 4=20=17+3$.

$\gcd(7,18)=1$, and $7\times 13=91=5\times 18+1$, so the inverse of $7$ modulo $18$ is $13$. Then $x\equiv 13\times 5=65=3\times 18+11\equiv 11\pmod{18}$. Check: $7\times 11=77=4\times 18+5$. Pitfall: trying to divide $5$ by $7$; modulo $18$, you never divide, you multiply by the inverse.

$d=\gcd(8,28)=4$, and $4$ divides $12$: there are $4$ solutions modulo $28$. Divide everything by $4$, modulus included: $2x\equiv 3\pmod 7$. The inverse of $2$ modulo $7$ is $4$, so $x\equiv 12\equiv 5\pmod 7$. Modulo $28$, the solutions are $5$, $12$, $19$ and $26$, and the smallest is $5$. Check: $8\times 5=40=28+12$. Pitfall: dividing $8$ and $12$ by $4$ while keeping the modulus $28$, which gives $2x\equiv 3\pmod{28}$, with no solution since $2x-3$ is odd.

For every integer $a$ and every integer $n>0$, there is a UNIQUE pair of integers $(q,r)$ such that $a=nq+r$ with $0\leq r<n$. Two things matter in this statement: existence and uniqueness on the one hand, and above all the BOUNDS on the remainder, between 0 included and $n$ excluded. Those bounds are what rule out a negative remainder, and they are what students forget when $a<0$.

$2026=12\times 168+10$, so $q=168$ and $r=10$: this is what the clock in the figure shows, where you go around 168 times before stopping on 10. For 7: $2026=7\times 289+3$, so $q=289$ and $r=3$. Always check by recomputing $nq+r$, which takes one second and catches every multiplication-table error.

For $-17$ divided by 5: the quotient must be chosen so that the remainder falls in $[0, 5)$. With $q=-4$: $-17=5\times(-4)+3$, so $r=3$. The knee-jerk division $-17=5\times(-3)-2$ would give $r=-2$, which is not a valid remainder. For $-1$ divided by 12: $-1=12\times(-1)+11$, so $r=11$: it is the last notch on the clock before going back through zero, which is exactly the picture to remember.

In PYTHON, $-17\ \%\ 5$ equals 3, the mathematical convention, since the divisor 5 is positive. In C and in JAVA, the operator returns $-2$, with the sign of the dividend. Both languages compute correctly; they simply do not answer the same question. The practical consequence for a programmer: circular indexing code written in C must correct the negative case, for example with $((a\ \%\ n)+n)\ \%\ n$, whereas the same code in Python works as is.

Days of the week are counted modulo 7. $100=7\times 14+2$, so in 100 days you move forward 2 notches: Tuesday plus 2 gives THURSDAY. 100 days ago, you move back 2 notches: Tuesday minus 2 gives SUNDAY. You can also write $-100\bmod 7=5$ and move forward 5, which also gives Sunday, since moving forward 5 or back 2 comes to the same thing on a cycle of 7.

DIVISIBILITY: $a\equiv b\pmod n$ means that $n$ divides $a-b$. REMAINDERS: it means that $a$ and $b$ leave the SAME remainder when divided by $n$. The two formulations are equivalent, and you must be able to switch from one to the other: the first is used in proofs, the second in calculations.

REFLEXIVE: $n$ divides $a-a=0$, so $a\equiv a$. SYMMETRIC: if $n$ divides $a-b$, it also divides $b-a=-(a-b)$, so $b\equiv a$. TRANSITIVE: if $n$ divides $a-b$ and $b-c$, it divides their sum $(a-b)+(b-c)=a-c$, so $a\equiv c$. These three properties make congruence an equivalence relation, whose classes are exactly the $n$ sets of numbers that leave the same remainder.

By hypothesis $a-b=kn$ and $c-d=\ell n$ for two integers $k$ and $\ell$. SUM: $(a+c)-(b+d)=(a-b)+(c-d)=(k+\ell)n$, a multiple of $n$ ✓. PRODUCT: $ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)=(ck+b\ell)n$, a multiple of $n$ ✓. The trick for the product is to add and subtract $bc$, which brings out both hypotheses; it is worth remembering, it will come up again elsewhere.

$17\equiv 2\pmod 5$, since $17=5\times 3+2$. Compatibility with products lets you raise both sides to the power 4: $17^{4}\equiv 2^{4}=16\equiv 1\pmod 5$. The remainder is therefore 1, while $17^{4}=83{,}521$, a number you never had to write down. That is the whole point of modular computation: reduce BEFORE multiplying, never after.

NO, division is not compatible in general. We do have $6\equiv 12\pmod 6$, since $12-6=6$. Dividing both sides by 2: $3\equiv 6\pmod 6$ would be false, because $6-3=3$ is not a multiple of 6. The correct rule is that you may cancel a factor $k$ provided you ALSO divide the modulus by $\gcd(k,n)$, or if $k$ is relatively prime to $n$. This restriction is what makes exercise 5 on inverses necessary.

The addition table modulo 5 is obtained by adding and then taking the remainder. Its first row, the row of 0, is $0,1,2,3,4$; the row of 1 is $1,2,3,4,0$; the row of 2 is $2,3,4,0,1$, and so on. YES, each row contains each element exactly once: adding a fixed number is a permutation, because you can always go back by adding its negative. This is true for every $n$, prime or not.

Checks: $3\times 5=15=14+1\equiv 1$; $4\times 6=24=21+3\equiv 3$; $2\times 4=8\equiv 1$. You observe that EACH ROW contains each nonzero element exactly once, and in particular that it contains 1. In other words, every nonzero element has an INVERSE modulo 7, which is far from obvious and will be the subject of exercise 5.

Modulo 6, the row of 2 gives $2,4,0,2,4$ for the multipliers $1,2,3,4,5$: it contains a ZERO even though neither factor is zero, and it does NOT contain 1. The row of 3 gives $3,0,3,0,3$, even worse. Only the rows of 1 and 5 contain 1. The table is therefore very different from the one modulo 7.

$2\times 3=6\equiv 0\pmod 6$, with $2\neq 0$ and $3\neq 0$. Such elements are called ZERO DIVISORS. They appear because 6 factors as $2\times 3$: the product collects all the factors of 6 and becomes a multiple of 6. Modulo 7 this is impossible, because 7 is PRIME: if 7 divides a product $ab$, it divides $a$ or $b$, a property that characterizes precisely the prime numbers.

An element $a$ is invertible modulo $n$ if and only if $\gcd(a,n)=1$. Consequently, ALL the nonzero elements are invertible if and only if $n$ is PRIME, in which case the integers modulo $n$ form a field. If $n$ is composite, the elements that share a factor with $n$ are not invertible and are zero divisors. This distinction is what makes prime moduli so valuable in cryptography and in error-correcting codes.

Let $r=a\bmod n$, so $a=nq+r$. If $d$ divides $a$ and $n$, then it divides $a-nq=r$, so it divides $n$ and $r$. Conversely, if $d$ divides $n$ and $r$, it divides $nq+r=a$, so it divides $a$ and $n$. The two pairs therefore have EXACTLY the same common divisors, and in particular the same greatest one. The algorithm then consists in replacing the pair by a smaller pair until the remainder becomes zero.

$1071=2\times 462+147$; $462=3\times 147+21$; $147=7\times 21+0$. The last nonzero remainder is 21, so $\gcd(1071,462)=21$. The figure gives the geometric reading: you tile the rectangle with smaller and smaller squares, and the side of the last square is the GCD. Three divisions were enough, where searching for the divisors of 1071 would have taken many more.

$240=5\times 46+10$; $46=4\times 10+6$; $10=1\times 6+4$; $6=1\times 4+2$; $4=2\times 2+0$. The GCD is 2. Note that these two numbers, smaller than those in question b, took MORE steps: the number of steps does not depend on the size of the numbers but on the sequence of quotients, all equal to 1 in the worst case.

Both versions fit in four lines and can be read straight off question a. The ITERATIVE version replaces the pair $(a,n)$ by $(n,a\bmod n)$ on every pass and stops when the second term becomes zero; the first one then holds the GCD. The RECURSIVE version translates the same equality word for word, with the base case $n=0$ returning $a$. The recursive version is more readable and its number of calls is the number of divisions, so it runs no risk of stack overflow for integers of reasonable size; the iterative version avoids that risk altogether and remains the form used in libraries.

Lamé's theorem states that the number of steps is at most about $5$ times the number of DIGITS of the smaller of the two numbers, which is remarkably few: fewer than 50 steps for ten-digit numbers. The WORST CASE is that of two consecutive FIBONACCI numbers, such as 89 and 55, for which every quotient equals 1, so the algorithm cannot speed anything up. It is a rare example where the worst case of an algorithm is known explicitly.