University Discrete Mathematics — Modular Arithmetic and Cryptography Worksheet

All 8 questions

Each question targets one named concept from the sheet. Read them here, or print the PDF — it has working space under each one.

1. Q1Congruences and Arithmetic Modulo n

   Recall that for an integer $n\ge 2$, $a\equiv b\left(\mathrm{mod}n\right)$ means $n\mid (a-b)$, and $amodn$ is the remainder $r$ with $0\le r<n$ and $a\equiv r\left(\mathrm{mod}n\right)$.

   1. Decide whether $83\equiv -7\left(\mathrm{mod}15\right)$.
   2. Decide whether $214\equiv 4\left(\mathrm{mod}12\right)$.
   3. Compute $(-45)mod8$.
   4. List every integer $x$ with $-20\le x\le 20$ and $x\equiv 3\left(\mathrm{mod}7\right)$.
2. Q2Congruences and Arithmetic Modulo n

   Without a calculator and without multiplying out, find:

   1. the remainder when $47·58+{39}^2$ is divided by $11$;
   2. $2^{50}mod7$;
   3. the last digit of $7^{83}$.
3. Q3Modular Inverses and Linear Congruences

   Use the extended Euclidean algorithm to find an inverse of $11$ modulo $26$, that is, an integer $s$ with $0\le s<26$ and $11s\equiv 1\left(\mathrm{mod}26\right)$. Check your answer.

4. Q4Modular Inverses and Linear Congruences

   Solve each congruence, giving every solution modulo the stated modulus, or show that there is none.

   1. $7x\equiv 5\left(\mathrm{mod}18\right)$
   2. $12x\equiv 20\left(\mathrm{mod}28\right)$
   3. $10x\equiv 7\left(\mathrm{mod}25\right)$
5. Q5Fermat's Little Theorem and Modular Exponentiation

   Fermat's little theorem states: if $p$ is prime and $p\nmid a$, then $a^{p-1}\equiv 1\left(\mathrm{mod}p\right)$.

   1. Compute $3^{45}mod17$ by repeated squaring: write $45$ in binary, tabulate $3^1,3^2,3^4,\dots mod17$, and multiply the powers you need.
   2. Use Fermat's little theorem to compute $7^{2026}mod13$.
6. Q6RSA Encryption and Decryption

   In RSA, one chooses distinct primes $p$ and $q$, sets $n=pq$, chooses $e$ with $gcd(e,(p-1)(q-1))=1$, and lets $d$ be the inverse of $e$ modulo $(p-1)(q-1)$. The public key is $(n,e)$, the private key is $d$. A message is an integer $m$ with $0\le m<n$; it is sent as $c=m^{e}modn$ and recovered as $m=c^{d}modn$.

   Take $p=5$ and $q=11$.

   1. Compute $n$ and $(p-1)(q-1)$, and explain why $e=5$ is not an allowed choice.
   2. With $e=3$, find the private key $d$.
   3. Encrypt the message $m=8$.
7. Q7RSA Encryption and Decryption

   An RSA key has public part $(n,e)=(77,7)$ and private key $d=43$. (A message $m$ with $0\le m<n$ is sent as $c=m^{e}modn$ and recovered as $m=c^{d}modn$.) You receive $c=37$. Decrypt it by repeated squaring, and check your answer by re-encrypting it.

8. Q8Synthesis — drawing on several topics in this unit

   Find every $x$ with $0\le x<13$ such that $5x\equiv 3^{100}\left(\mathrm{mod}13\right)$.

The 6 challenge problems for this topic are a separate, paid sheet and are not reproduced here.

How to do every concept on this sheet

This is the part worksheet sites usually leave out. Below is the actual reasoning behind each group of questions — not a full solution set, the decisions that get you to one. Read it before you start, or after you get stuck.

Two meanings of "mod", and why both are needed

The same three letters do two different jobs. As a relation, a ≡ b (mod n) is a statement about a pair of integers: it is true exactly when n divides their difference. As an operation, a mod n is a single number — the remainder the division algorithm produces, pinned to the range from 0 up to but not including n. Q1 opens with both definitions written out and then asks you to use each one.

Q1(d) shifts from a yes-or-no question to a set. Everything congruent to a fixed value modulo 7 sits on an arithmetic progression with common difference 7, so start from the stated value and step up and down by the modulus until you leave the interval at both ends. Listing them is worth doing deliberately: that list is one equivalence class of congruence modulo 7, which is the connection back to Sets, Functions and Relations.

Reducing before you multiply

The reason modular arithmetic is usable at all is that it respects the operations. If a ≡ b and c ≡ d modulo the same n, then the sums are congruent and so are the products — and, by repeating the product rule, so are the powers. That licence is what Q2 is built to exercise, and its instruction not to multiply out is the point of the question rather than a restriction on it.

Q2(a) is steps 1 and 2 on a sum of a product and a square. Q2(b) is step 3: find where the powers of 2 return to 1 modulo 7, divide the exponent 50 by that cycle length, and let the remainder pick the answer out of the short list you already built. Q2(c) is the same idea in disguise — the last decimal digit of a number is that number modulo 10, so the question is really asking for 7⁸³ mod 10, and the powers of 7 cycle quickly there too.

Modular inverses and the extended Euclidean algorithm

Division has no direct meaning modulo n. What replaces it is an inverse: a number s with a·s ≡ 1 (mod n). It exists exactly when a and n are coprime, and the reason is Bézout's identity from Divisibility and Primes — the extended Euclidean algorithm produces integers s and t with a·s + n·t = gcd(a, n), and when that gcd is 1, reading the identity modulo n makes the n·t term vanish and leaves a·s ≡ 1.

Q3 also asks you to check the answer, and that instruction is not decoration. Multiply your candidate by 11, reduce modulo 26, and confirm you land on 1. The check costs one line and catches every sign error the back-substitution can make.

Linear congruences: none, one, or several

Q4 asks for every solution modulo the stated modulus, or a demonstration that there is none, and the three parts are deliberately different cases. The single fact that decides which case you are in is the gcd of the coefficient and the modulus.

Each part of Q4 deserves the same opening line — the gcd of the coefficient and the modulus — written down before any attempt to solve. It tells you in one step which of the three endings the part has, and it costs less than discovering it halfway through.

Fermat's little theorem and repeated squaring

Two tools bring an enormous exponent down to size, and Q5 puts one in each part so that the difference between them is visible. Repeated squaring works for any modulus; Fermat's little theorem is sharper but needs a prime modulus and a base the prime does not divide.

Q5(a) spells out the repeated-squaring routine, which is worth learning as a fixed procedure. Write the exponent in binary; that tells you which powers of the base you need. Build a short table of a, a², a⁴, a⁸ and so on, each entry the square of the one above it reduced modulo the modulus immediately. Then multiply together only the table entries whose binary bit is 1, reducing after each multiplication. The table is never longer than the number of binary digits, which is why the method scales.

Q5(b) is the Fermat route. Check the hypotheses first — the modulus 13 is prime and it does not divide 7 — then divide the exponent 2026 by 12 and write the exponent as 12 times the quotient plus a remainder. The theorem collapses the whole first part to 1, and only the small leftover power is left to compute. The arithmetic that remains is a few lines.

Building an RSA key pair

Q6 states the whole scheme in its opening paragraph and then walks you through it with two small primes, so nothing is a black box. The three quantities that matter are n = pq, which is public; (p − 1)(q − 1), which is the modulus the exponents live in and must stay secret; and the pair e, d, which are inverses of each other modulo that second number.

Q6(a) asks for both moduli and then for a reason a particular exponent is not allowed. Compute (p − 1)(q − 1) first, then test the proposed e against the coprimality condition in step 3 — the explanation is whatever that gcd calculation shows, stated as a sentence rather than as a number. Q6(b) is Q3's extended Euclidean algorithm again, run in the exponent modulus. Q6(c) is a modular exponentiation with a small exponent: reduce as you go and finish inside the range 0 ≤ c < n.

Decrypting, and checking that you did

Q7 hands you a complete key pair and a ciphertext, and asks for the plaintext by repeated squaring. The private exponent is large enough that Q5(a)'s table is the only sensible route: write 43 in binary, build the table of squares of the ciphertext modulo 77, and multiply the selected rows together.

Then do what the question asks and re-encrypt. Raising your recovered plaintext to the public exponent modulo n must return the ciphertext you started from. This is a genuine verification rather than a formality: the two exponentiations use different exponents and different tables, so an arithmetic slip in one will not be reproduced by the other. Any question in this sheet that produces a message can be checked this way, and a solution that shows the check is a stronger piece of writing than one that does not.

The synthesis question

Q8 needs both halves of the set in one line of work. The right side is a large power modulo a prime, so it is handled by Fermat's little theorem exactly as in Q5(b) — reduce the exponent against p − 1 first, and a manageable power is left. The left side is then a linear congruence in the shape of Q4: compute the gcd of the coefficient and the modulus to establish how many solutions there are, find the inverse of the coefficient by the extended Euclidean algorithm, and multiply through.

Preview all 5 pages

Click any page to open the full PDF.

Getting the most out of it

Reduce early and reduce often

The habit that makes every question in this set easy is replacing each number by its remainder before doing anything with it, and again after each operation. Nothing larger than the modulus should ever appear in your work. If a big number has appeared, you have made the question harder than it was set.

Write the gcd first

Whether an inverse exists, whether a linear congruence has solutions, how many it has, and whether an RSA exponent is legal are all the same question about a gcd. Make computing it the first line of any of those questions, before you decide what method to use.

Check by substituting back

Every answer in this set is checkable in one line: multiply the inverse by the original number, substitute the solution into the congruence, re-encrypt the message you decrypted. These checks are cheap and they catch precisely the arithmetic slips that modular work invites, so build them into the answer rather than leaving them for a spare moment.

Keep a table of small powers

For each modulus you meet, jotting down the first several powers of the base takes under a minute and often reveals a short cycle that makes the rest of the question trivial. It is also the table repeated squaring needs, so the work is never wasted.

Say which modulus you are in

In the RSA questions two moduli are live at once, n for messages and (p − 1)(q − 1) for exponents. Label every congruence you write with its modulus. Marks in this chapter are lost far more often to working in the wrong one than to bad arithmetic.

Common questions