Mathematics for Computer Science 201-N11 • CEGEP, Montreal

Revision sheet: modular arithmetic (201-N11)

Q: Can the remainder of a division be negative?

No, never in mathematics: Euclidean division requires a remainder between zero and the modulus minus one. Minus seventeen modulo five is therefore three, not minus two. The percent operator of the C, C plus plus and Java languages does return a negative remainder in that case, unlike Python: it is a programming convention, not a definition.

Q: Can you cancel a common factor in a congruence?

Only if that factor is relatively prime to the modulus. Otherwise, you also divide the modulus by the greatest common divisor of the factor and the modulus. For example, four times two and four times five are congruent modulo six, whereas two and five are not: they become congruent only modulo three.

Q: How do you compute a modular inverse?

First check that the number is relatively prime to the modulus, otherwise the inverse does not exist. Then run the Euclidean algorithm and work back up the equalities to write one equals a times u plus n times v. The coefficient u is the inverse, which you reduce between zero and the modulus minus one, then check by multiplication.

Q: How do you compute a very large power modulo n?

You never compute the whole power. If the modulus is prime and does not divide the base, Fermat's little theorem lets you reduce the exponent modulo the modulus minus one. You finish with fast exponentiation, which squares and reduces at every step, with about twice as many multiplications as the base-two logarithm of the exponent.

Q: How many solutions does a linear congruence have?

It has exactly as many as the greatest common divisor of the coefficient and the modulus, provided that this divisor also divides the right-hand side; otherwise it has none. You then divide both sides and the modulus by this divisor, solve, and unfold the solution obtained by adding the reduced modulus.

Modular arithmetic is not hard to understand: it is clock arithmetic. It is hard to HANDLE, because three operations out of four behave as usual and the fourth one, division, does not exist at all.

This sheet is written for CEGEP students taking 201-N11 in a computer science program (Computer Science Technology, Techniques de l'informatique), and for anyone who comes to cryptography through mathematics. The corrected exercise set on the same chapter then puts every reflex to the test.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next, tells you which chapter to tackle next and lets you ask for the method or exercise you are missing. Create your space, an email is enough.

The thread of the chapter

Working modulo $n$ means replacing an integer by its remainder and computing with remainders. Addition and multiplication go through without trouble; DIVISION never does, and that is where almost every lost mark comes from.

This chapter is part of 201-N11, Mathematics for Computer Science

The essentials

Euclidean division: the remainder is ALWAYS nonnegative

• For $n>0$ , there is a unique pair $(q, r)$ such that $a=nq+r$ with $0\leq r<n$ .
• This also holds for $a<0$ : $-17=5\times(-4)+3$ , so $-17\bmod 5=3$ , not $-2$ .
• The $\%$ operator of the C, C++ and Java languages does NOT follow this convention and returns a remainder with the sign of the dividend. Python does follow it.
• The quotient is the FLOOR of $\frac{a}{n}$ : $\left\lfloor\frac{-17}{5}\right\rfloor=-4$ , not $-3$ .

Dividing

-17

5

gives

q=-4

and

r=3

, never

r=-2

: the remainder is counted from the multiple located to the LEFT, so it is always nonnegative.

On a test, a negative remainder is a wrong answer even when the calculator displays it. Adding the modulus until you land back in $[0, n-1]$ takes five seconds.

Congruences: what goes through, and what does not

• $a\equiv b\pmod n$ means that $n$ divides $a-b$ , in other words that $a$ and $b$ leave the same remainder.
• COMPATIBLE with addition, subtraction, multiplication and therefore powers: you reduce BEFORE computing, never after.
• NOT compatible with division: $\frac{a}{b}\pmod n$ makes no sense in general.
• CANCELLATION: from $ac\equiv bc\pmod n$ you can conclude $a\equiv b\pmod n$ only if $\gcd(c,n)=1$ . Otherwise you must divide the modulus by $\gcd(c,n)$ .

Modulo

5

, the wheel has only five positions:

-3

2

7

and

12

land on the same spot, they are congruent to one another, with the same remainder

2

Reducing before computing is also what makes the calculations feasible: $7^{50}\bmod 13$ can be done in your head by reducing at every step, and overflows the calculator if you compute $7^{50}$ first.

Euclid, Bézout, inverse: one machine with three uses

• EUCLID: $\gcd(a,n)=\gcd(n,a\bmod n)$ , repeated until the remainder is zero. The number of steps is at most about five times the number of digits.
• BÉZOUT: there exist $u$ and $v$ such that $au+nv=\gcd(a,n)$ , obtained by working back up the EXTENDED Euclidean algorithm.
• INVERSE: $a$ is invertible modulo $n$ if and only if $\gcd(a,n)=1$ , and the inverse is then Bézout's $u$ , reduced into $[0, n-1]$ .
• All the nonzero elements are invertible IF AND ONLY IF $n$ is prime. Otherwise ZERO DIVISORS appear, such as $2\times 3\equiv 0\pmod 6$ .

The Euclidean algorithm tiles the

48\times 18

rectangle with squares:

48=2\times 18+12

, then

18=1\times 12+6

, then

12=2\times 6

. The side of the last square is the GCD, here

6

Fermat, fast exponentiation and linear congruences

• FERMAT: if $p$ is PRIME and does not divide $a$ , then $a^{p-1}\equiv 1\pmod p$ .
• In practice: reduce the BASE modulo $p$ and the EXPONENT modulo $p-1$ . Two different moduli, the trap of the chapter.
• FAST EXPONENTIATION: $a^{e}\bmod n$ in about $2\log_{2}e$ multiplications, by squaring and reducing at every step.
• CONGRUENCE $ax\equiv b\pmod n$ : it has solutions if and only if $d=\gcd(a,n)$ divides $b$ , and then it has exactly $d$ of them modulo $n$ .

By successive squaring,

7^{8}

modulo

13

takes three multiplications, reduced at every step: you never handle a number larger than

12^{2}

For a modulus that is not prime, Euler's theorem replaces Fermat's, with $\varphi(n)$ in place of $p-1$ . Applying Fermat as is to a composite modulus is wrong.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. Giving a negative remainder

1 mark each time, and a wrong encryption in an RSA problem

What not to write

“ $-17\bmod 5=-2$ , that's what my calculator shows.”

What to write

“ $-17=5\times(-4)+3$ , so $-17\bmod 5=3$ : the remainder of a Euclidean division always belongs to $[0, n-1]$ .”

Why: The $\%$ operator of the C family of languages returns a remainder with the sign of the dividend, which is not the mathematical definition. In Python and in mathematics, the remainder is nonnegative.

2. Cancelling a factor that is not relatively prime to the modulus

the whole question

What not to write

“ $4\times 2\equiv 4\times 5\pmod 6$ , so $2\equiv 5\pmod 6$ .”

What to write

“ $\gcd(4, 6)=2\neq 1$ : no cancelling. Divide the MODULUS by $2$ and you get $2\equiv 5\pmod 3$ , which is true.”

Why: Modulo $6$ , $8$ and $20$ do leave the same remainder $2$ , whereas $2$ and $5$ are not congruent: cancelling loses information as soon as the factor shares a divisor with the modulus.

3. Dividing in a congruence

1 mark here, the whole question as soon as the result is not an integer

What not to write

“ $3x\equiv 6\pmod 7$ , so $x\equiv\frac{6}{3}=2$ .”

What to write

“MULTIPLY by the inverse of $3$ modulo $7$ , which is $5$ since $3\times 5=15\equiv 1$ : $x\equiv 5\times 6=30\equiv 2\pmod 7$ .”

Why: Division does not exist modulo $n$ . The shortcut works by luck when the quotient comes out even, and it collapses as soon as it does not: $3x\equiv 5\pmod 7$ has nothing to do with $\frac{5}{3}$ .

4. Reducing the exponent modulo $p$ instead of $p-1$

the whole question

What not to write

“ $3^{100}\bmod 7$ : I reduce $100$ modulo $7$ , which gives $2$ , so $3^{2}=9\equiv 2$ .”

What to write

“The base is reduced modulo $7$ , the EXPONENT modulo $7-1=6$ . Since $100=6\times 16+4$ , $3^{100}\equiv 3^{4}=81\equiv 4\pmod 7$ .”

The powers

3^{k}\bmod 7

repeat identically every SIX steps, and

6=7-1

: that is Fermat's little theorem. So the exponent is reduced modulo

p-1

, the base modulo

p

Why: Fermat's little theorem says $a^{p-1}\equiv 1$ , so it is the period $p-1$ that governs the exponent. Two moduli live side by side in the same calculation, and mixing them up gives a plausible, wrong result.

5. Believing that every nonzero element is invertible

the whole question, and a calculation that cannot succeed

What not to write

“Modulo $6$ , I look for the inverse of $2$ to solve $2x\equiv 4$ .”

What to write

“ $\gcd(2, 6)=2\neq 1$ : $2$ is NOT invertible modulo $6$ . It is even a zero divisor, since $2\times 3\equiv 0\pmod 6$ .”

Modulo

6

, the red cells are ZERO products of nonzero factors:

2

3

and

4

are zero divisors, and have no inverse.

Why: Being invertible modulo $n$ is exactly being relatively prime to $n$ . With a composite modulus, some of the elements have no inverse, and the congruence is then solved through the Bézout condition, not through an inverse.

6. Applying Fermat without checking its two hypotheses

the whole question, and a wrong conclusion in cryptography

What not to write

“ $a^{n-1}\equiv 1\pmod n$ for every $a$ and every $n$ .”

What to write

“The theorem requires $n$ PRIME and $n$ not dividing $a$ . Modulo $6$ , which is not prime, $2^{5}=32\equiv 2$ , not $1$ .”

Why: With a composite modulus, it is Euler's theorem that applies, with $\varphi(n)$ in place of $p-1$ . Using Fermat outside its scope gives a result that looks like an answer.

7. Computing the whole power before reducing

your whole test time, and a calculator that overflows

What not to write

“ $7^{50}\bmod 13$ : I compute $7^{50}$ , then I divide by $13$ .”

What to write

“I reduce at EVERY step: $7^{2}=49\equiv 10$ , $7^{4}\equiv 10^{2}=100\equiv 9$ , and so on by successive squaring.”

Why: $7^{50}$ has more than forty digits: no exam calculator gives it exactly, and rounding makes the remainder wrong. The compatibility of congruence with multiplication exists precisely to avoid this.

8. Announcing a single solution to a linear congruence

half the marks for the question

What not to write

“ $14x\equiv 30\pmod{100}$ : I find $x\equiv 45$ , that's the solution.”

What to write

“ $d=\gcd(14, 100)=2$ divides $30$ , so there are exactly TWO solutions modulo $100$ : $x\equiv 45$ and $x\equiv 95$ .”

14x\equiv 30\pmod{100}

has

d=2

solutions:

45

and

95

\frac{100}{2}=50

apart.

Why: The number of solutions modulo $n$ is $d=\gcd(a,n)$ as soon as $d$ divides $b$ . Solving the reduced congruence gives one solution modulo $\frac{n}{d}$ , which must then be unfolded into $d$ solutions modulo $n$ .

Which method to choose

What you may do in a congruence

Before each manipulation, look at which operation it is. Three are free, one is forbidden, two are conditional.

If addition, subtraction, multiplication → free: reduce each term BEFORE computing

Example: $17\times 23\equiv 2\times 3=6\pmod 5$
If raising to a power, any modulus → free on the BASE, reducing at each squaring; the exponent, however, cannot be reduced without a hypothesis

Example: $7^{4}\equiv 10^{2}\equiv 9\pmod{13}$
If reducing the EXPONENT, prime modulus $p$ not dividing $a$ → allowed modulo $p-1$ , by Fermat's little theorem

Example: $3^{100}\equiv 3^{4}\equiv 4\pmod 7$

For a composite modulus, replace $p-1$ by $\varphi(n)$ and check that $\gcd(a,n)=1$ .
If cancelling a common factor $c$ → allowed only if $\gcd(c,n)=1$ ; otherwise ALSO divide the modulus by $\gcd(c,n)$

Example: $4\times 2\equiv 4\times 5\pmod 6$ gives $2\equiv 5\pmod 3$
If division → FORBIDDEN. Multiply by the inverse, which exists only if $\gcd(a,n)=1$

Example: $3x\equiv 6\pmod 7$ is solved by $\times 5$ , not by $\div 3$

When the inverse does not exist, the congruence is not necessarily unsolvable: it has $\gcd(a,n)$ solutions as soon as this GCD divides the right-hand side. That is the most frequent case on tests.

Which tool for what the question asks

The questions of the chapter come down to six forms, and each one has a single tool. Identify it before writing the first line.

If “what is the remainder of”, “what day of the week” → Euclidean division, then reducing the calculation modulo $n$

Example: $2^{1000}\bmod 7$ by periodicity
If “compute $\gcd(a,b)$ ” → Euclidean algorithm, as a table of successive remainders

Example: $\gcd(48, 18)=6$ in three divisions
If “find $u$ and $v$ such that $au+nv=d$ ” → EXTENDED Euclidean algorithm, working back up the equalities

Example: $50-7\times 7=1$ gives $u=-7$
If “the inverse of $a$ modulo $n$ ” → check $\gcd(a,n)=1$ , then Bézout: the inverse is $u$ reduced into $[0, n-1]$

Example: the inverse of $7$ modulo $50$ is $-7\equiv 43$
If “solve $ax\equiv b\pmod n$ ” → compute $d=\gcd(a,n)$ ; if $d\nmid b$ , no solution; otherwise divide everything by $d$ , invert, then unfold into $d$ solutions

Example: $14x\equiv 30\pmod{100}$ gives $x\equiv 45$ and $x\equiv 95$
If “a huge exponent” → Fermat to reduce the exponent, then fast exponentiation to finish

Example: $3^{100}\bmod 7$ comes down to $3^{4}$

All these questions start with the same move: computing a GCD. It decides whether the inverse exists, how many solutions the congruence has, and whether Fermat applies.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Computing a modular inverse by the extended Euclidean algorithm

When to use it: The question asks for the inverse of $a$ modulo $n$ , or a solution that depends on it.

1 Check existence BEFORE computing: “ $\gcd(7, 50)=1$ , so $7$ is invertible modulo $50$ .”
2 Run the Euclidean algorithm, writing out each division: “ $50=7\times 7+1$ , then $7=1\times 7+0$ .”
3 Work back up to isolate the GCD: “ $1=50-7\times 7$ .”
4 Read Bézout's identity modulo $n$ : “so $-7\times 7\equiv 1\pmod{50}$ .”
5 Reduce the coefficient into $[0, n-1]$ and CHECK: “ $-7\equiv 43$ , and $7\times 43=301=6\times 50+1$ .”

Concluding sentence

The inverse of $7$ modulo $50$ is $43$ , since $7\times 43=301\equiv 1\pmod{50}$ .

The trap: Giving a negative Bézout coefficient as the inverse. It is correct, but an inverse is written in $[0, n-1]$ , and the final check by multiplication is the only way to make sure you have not swapped $u$ and $v$ .

Marking: Usually 1 mark for checking the GCD, 1 mark for running the algorithm, 1 mark for the back substitution, 1 mark for the reduced and checked inverse.

Solving a linear congruence $ax\equiv b\pmod n$

When to use it: Any linear congruence modulo $n$ , including one disguised as a check-digit or calendar problem.

1 Compute $d=\gcd(a,n)$ and DECIDE: “ $d=2$ divides $30$ , so there are solutions, exactly $2$ modulo $100$ .”
2 Divide all three quantities by $d$ , modulus included: “ $7x\equiv 15\pmod{50}$ .”
3 Compute the inverse of $\frac{a}{d}$ modulo $\frac{n}{d}$ by the extended Euclidean algorithm.
4 Multiply and reduce: “ $x\equiv 43\times 15\equiv 45\pmod{50}$ .”
5 UNFOLD the $d$ solutions modulo $n$ by adding $\frac{n}{d}$ , then check each one in the original congruence.

Concluding sentence

The congruence $14x\equiv 30\pmod{100}$ has exactly two solutions, $x\equiv 45\pmod{100}$ and $x\equiv 95\pmod{100}$ .

The trap: Forgetting to divide the MODULUS along with both sides. You then get $7x\equiv 15\pmod{100}$ , whose solution does satisfy the original congruence but leaves out the other one: you lose solutions.

Marking: 1 mark for the existence condition, 1 mark for dividing by $d$ modulus included, 1 mark for the inverse, 1 mark for unfolding the $d$ solutions.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

Check that the remainder lies in $[0, n-1]$

Reread every remainder written on your paper: a negative number, or one greater than or equal to the modulus, is a mistake, whatever calculator produced it.

A $-2$ modulo $5$ is corrected by adding $5$ , which gives $3$ . A $7$ modulo $5$ is corrected by subtracting $5$ , which gives $2$ .
Check an inverse by multiplying

Multiply $a$ by the inverse you found and reduce: the result must be exactly $1$ . It is immediate and it catches every error in the Bézout back substitution.

$7\times 43=301=6\times 50+1$ : correct. If you had given $-7$ without reducing it, the check would also pass, but the answer would not be accepted as written.
Check Bézout by recomputing the combination

Put $u$ and $v$ back into $au+nv$ and compare with the GCD you announced. A sign error shows up immediately, and it is the most frequent error in the back substitution.

$7\times(-7)+50\times 1=-49+50=1$ : matches the GCD. A result of $7\times 7+50\times 1=99$ would show that the sign of $u$ was lost.
Check a power through periodicity

Compute the first powers of the base and spot the rank at which you get back to $1$ . That rank divides $p-1$ and lets you recompute the result another way.

The powers of $3$ modulo $7$ give $3$ , $2$ , $6$ , $4$ , $5$ then $1$ : the period is $6$ , so $3^{100}=3^{96}\times 3^{4}\equiv 3^{4}\equiv 4$ .

The typical problem, taken apart

Solving $14x\equiv 30\pmod{100}$ , down to both solutions

Solve in $\mathbb{Z}$ the linear congruence $14x\equiv 30\pmod{100}$ .

State the exact number of solutions modulo $100$ and check each one.

Step 1

$\gcd(14, 100)$ : $100=7\times 14+2$ , then $14=7\times 2+0$ , so $d=2$ . Since $2$ divides $30$ , the congruence has solutions, and it has exactly $d=2$ of them modulo $100$ .

Why

This first line decides everything: it says whether there are solutions and how many. A paper that skips it can find the right value and still lose half the marks, because it never counted the solutions.

Step 2

Divide BOTH sides and the MODULUS by $d=2$ : $7x\equiv 15\pmod{50}$ .

Why

The modulus is divided too, otherwise the resulting congruence is not equivalent. That omission is what makes solutions go missing.

Step 3

$\gcd(7, 50)=1$ , so $7$ is invertible modulo $50$ . Euclid: $50=7\times 7+1$ , so $1=50-7\times 7$ and $-7\times 7\equiv 1\pmod{50}$ .

Why

Check invertibility before looking for the inverse. After dividing by $d$ it is guaranteed, but writing it down earns the rigour mark and proves that the condition was understood.

Step 4

The inverse of $7$ modulo $50$ is therefore $-7\equiv 43$ . Check: $7\times 43=301=6\times 50+1$ .

Why

Reduce into $[0, 49]$ and check by multiplication. These two moves take ten seconds and eliminate every sign error in the back substitution.

Step 5

Multiply the congruence by $43$ : $x\equiv 43\times 15=645\pmod{50}$ , and $645=12\times 50+45$ , so $x\equiv 45\pmod{50}$ .

Why

You multiply, you never divide. The result here is a congruence modulo $50$ , not modulo $100$ : the question is not finished yet, and this is where half the papers stop.

Step 6

Unfold modulo $100$ : $x\equiv 45$ and $x\equiv 45+50=95$ . That makes $d=2$ solutions, as announced in the first line.

Why

Unfolding means adding $\frac{n}{d}$ as many times as needed. The count announced at the start serves as a check here: two solutions expected, two solutions obtained.

Step 7

Check: $14\times 45=630=6\times 100+30$ and $14\times 95=1330=13\times 100+30$ . Both values work.

Why

Substitute each solution into the ORIGINAL congruence, not into the reduced one. It catches arithmetic slips; a missing solution, however, only the count of the first line can reveal.

The conclusion, written out

The congruence $14x\equiv 30\pmod{100}$ has exactly two solutions modulo $100$ : $x\equiv 45$ and $x\equiv 95$ .

The classic mistake on this problem: Dividing only both sides and keeping the modulus: $7x\equiv 15\pmod{100}$ . The inverse of $7$ modulo $100$ is also $43$ , and you get $x\equiv 45\pmod{100}$ , so a single solution instead of two. The check in the original congruence reveals nothing, since $45$ works: only the condition on the GCD flags the missing solution.

Learn by heart

• The remainder of a Euclidean division is ALWAYS in $[0, n-1]$ , even for a negative dividend.
• Reduce BEFORE computing: congruence goes through addition and multiplication, never through division.
• $ac\equiv bc\pmod n$ gives $a\equiv b$ only if $\gcd(c,n)=1$ ; otherwise you divide the modulus too.
• $a$ is invertible modulo $n$ if and only if $\gcd(a,n)=1$ , and the inverse is Bézout's $u$ .
• All the nonzero elements are invertible if and only if $n$ is PRIME; otherwise there are zero divisors.
• Fermat: $p$ prime and $p\nmid a$ give $a^{p-1}\equiv 1\pmod p$ . Base modulo $p$ , EXPONENT modulo $p-1$ .
• $ax\equiv b\pmod n$ has solutions if and only if $\gcd(a,n)$ divides $b$ , and then exactly $\gcd(a,n)$ of them.
• Everything starts with a GCD: it decides the inverse, the number of solutions and whether Fermat can be used.

Frequently asked questions

Can the remainder of a division be negative?

No, never in mathematics: Euclidean division requires a remainder between zero and the modulus minus one. Minus seventeen modulo five is therefore three, not minus two. The percent operator of the C, C plus plus and Java languages does return a negative remainder in that case, unlike Python: it is a programming convention, not a definition.

Can you cancel a common factor in a congruence?

Only if that factor is relatively prime to the modulus. Otherwise, you also divide the modulus by the greatest common divisor of the factor and the modulus. For example, four times two and four times five are congruent modulo six, whereas two and five are not: they become congruent only modulo three.

How do you compute a modular inverse?

First check that the number is relatively prime to the modulus, otherwise the inverse does not exist. Then run the Euclidean algorithm and work back up the equalities to write one equals a times u plus n times v. The coefficient u is the inverse, which you reduce between zero and the modulus minus one, then check by multiplication.

How do you compute a very large power modulo n?

You never compute the whole power. If the modulus is prime and does not divide the base, Fermat's little theorem lets you reduce the exponent modulo the modulus minus one. You finish with fast exponentiation, which squares and reduces at every step, with about twice as many multiplications as the base-two logarithm of the exponent.

How many solutions does a linear congruence have?

It has exactly as many as the greatest common divisor of the coefficient and the modulus, provided that this divisor also divides the right-hand side; otherwise it has none. You then divide both sides and the modulus by this divisor, solve, and unfold the solution obtained by adding the reduced modulus.

Practise it

Corrected exercises: Modular arithmetic, 201-N11

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

12 corrected exercises
120 points
150 minutes

Do the exercises

Something missing from this sheet? A method, a trap, an exercise to practise it, a mistake you spotted: tell me, I read every request.

Sending goes through your free space: that is how I can answer you and tell you when the exercise is added. An email is enough, no password. Create your space. Rather not create an account? Write to me directly.

Previous sheet Number systems in computing Next sheet Set theory and relations

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/cegep-n11-modular-arithmetic. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

Looking for a 201-N11 tutor in Montreal?

Get in touch for a first session. We work on modular arithmetic at the level of real CEGEP tests, from congruences all the way to the extended Euclidean algorithm and RSA.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: modular arithmetic (201-N11)

The essentials

Euclidean division: the remainder is ALWAYS nonnegative

Congruences: what goes through, and what does not

Euclid, Bézout, inverse: one machine with three uses

Fermat, fast exponentiation and linear congruences

The mistakes that cost marks

1. Giving a negative remainder

2. Cancelling a factor that is not relatively prime to the modulus

3. Dividing in a congruence

4. Reducing the exponent modulo ppp instead of p−1p-1p−1

5. Believing that every nonzero element is invertible

6. Applying Fermat without checking its two hypotheses

7. Computing the whole power before reducing

8. Announcing a single solution to a linear congruence

Which method to choose

What you may do in a congruence

Which tool for what the question asks

How the answer is expected to be written

Computing a modular inverse by the extended Euclidean algorithm

Solving a linear congruence ax≡b(modn)ax\equiv b\pmod nax≡b(modn)

Check before you hand in

The typical problem, taken apart

Solving 14x≡30(mod100)14x\equiv 30\pmod{100}14x≡30(mod100), down to both solutions

Learn by heart

Frequently asked questions

Can the remainder of a division be negative?

Can you cancel a common factor in a congruence?

How do you compute a modular inverse?

How do you compute a very large power modulo n?

How many solutions does a linear congruence have?

Corrected exercises: Modular arithmetic, 201-N11

See also

Looking for a 201-N11 tutor in Montreal?

4. Reducing the exponent modulo $p$ instead of $p-1$

Solving a linear congruence $ax\equiv b\pmod n$

Solving $14x\equiv 30\pmod{100}$ , down to both solutions