University Discrete Mathematics — Divisibility and Primes 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. Q1Divisibility and the Division Algorithm

   The division algorithm says: for integers $a$ and $b$ with $b>0$ there are unique integers $q$ and $r$ with $a=bq+r$ and $0\le r<b$. For each dividend $a$ below, with $b=23$, find $q$ and $r$, and say whether $23\mid a$.

   1. $a=317$
   2. $a=-317$
   3. $a=-92$
2. Q2Divisibility and the Division Algorithm

   An integer $n$ leaves remainder $7$ when divided by $9$. Using $n=9q+7$ for some integer $q$, find the remainder when each of the following is divided by $9$.

   1. $4n+5$
   2. $n^2$
   3. $-n$
3. Q3Primes and the Fundamental Theorem of Arithmetic
   1. Decide whether $437$ and $401$ are prime. Test only the divisors you need, and say why testing those is enough.
   2. Let $A=2^3·3^2·5·7^2$ and $B=2·3^4·7^3·11$. Write $gcd(A,B)$ and $lcm(A,B)$ as products of prime powers, and find the number of positive divisors of $A$.

   Use: a positive integer $d$ divides $n=p_1^{e_1}\cdots p_k^{e_k}$ exactly when $d=p_1^{f_1}\cdots p_k^{f_k}$ with $0\le f_i\le e_i$ for every $i$, so $n$ has $(e_1+1)(e_2+1)\cdots (e_k+1)$ positive divisors.

4. Q4The Greatest Common Divisor and the Euclidean Algorithm

   Use the Euclidean algorithm to find $gcd(1573,1144)$. Show each division.

5. Q5The Greatest Common Divisor and the Euclidean Algorithm
   1. Use the Euclidean algorithm to find $gcd(4389,2002)$.
   2. Use $gcd(a,b)·lcm(a,b)=ab$ (for positive $a$, $b$) to find $lcm(4389,2002)$.
   3. The gcd of two integers, not both zero, is the largest positive integer dividing both. Find $gcd(-4389,2002)$ and $gcd(2002,0)$.
6. Q6Bezout's Identity and the Extended Euclidean Algorithm

   Use the extended Euclidean algorithm to find $gcd(391,299)$ and integers $x$, $y$ with $391x+299y=gcd(391,299)$.

7. Q7Bezout's Identity and the Extended Euclidean Algorithm

   Bezout's identity says the integers of the form $ax+by$, with $x,y\in \mathbb{Z}$, are exactly the multiples of $gcd(a,b)$.

   1. Explain why $18x+42y=100$ has no integer solution.
   2. Find one integer solution of $18x+42y=30$.
8. Q8Synthesis — drawing on several topics in this unit
   1. Use the Euclidean algorithm to find $gcd(1309,1001)$, and write it in the form $1309x+1001y$ with $x,y\in \mathbb{Z}$.
   2. Given that $1001=7·11·13$, use your gcd to write $1309$ as a product of primes, and find $lcm(1309,1001)$.

The 5 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.

The division algorithm, and what makes it an algorithm

The statement Q1 quotes is a theorem about existence and uniqueness: for integers a and b with b > 0 there is exactly one pair q, r with a = bq + r and 0 ≤ r < b. The constraint on r is what makes the pair unique, and it is the whole content of the question. Divisibility is then a special case of it: b | a means the remainder is zero, nothing more.

Q1 asks in each part whether 23 | a, and that is answered by the value of r alone, so do not answer it separately by eye. Note that b = 23 is fixed across the three parts and one part's dividend is the negative of another's: it is worth asking yourself, once both are done, how the two pairs (q, r) are related, because that relationship is a small theorem you will use again.

Carrying a remainder through an expression

Q2 is the first real use of the division algorithm as a tool. You are told only that an integer n leaves remainder 7 on division by 9, and asked for the remainders of 4n + 5, n² and −n. The nothing-else-known is deliberate: the answer must hold for every such n.

Testing one convenient value of n is a good way to catch an arithmetic slip, but it is not an argument: a single n cannot show that the remainder is the same for all of them. The algebra above is the proof, and it is a direct proof of exactly the kind Methods of Proof drills.

Primes, trial division, and knowing when to stop

Q3(a) asks you to decide primality for two three-digit numbers and — the harder half — to say why the divisors you tested were enough. The justification is the mathematics here; the arithmetic is bookkeeping.

So for each number in Q3(a): estimate √n by squaring candidates rather than reaching for a decimal, list the primes up to it, and divide by each. Write the short list of primes you tested and the sentence justifying it; a bare verdict with no list answers only half of what was asked.

The fundamental theorem of arithmetic, and reading gcd, lcm and divisors off it

Every integer above 1 is a product of primes in exactly one way up to order. Uniqueness is what makes the rest of Q3(b) mechanical: once two numbers are written over the same set of primes — giving a prime exponent 0 when it is absent — every question about their common factors is a question about exponents, one prime at a time.

Q3(b) gives A and B already factored, so no factoring is needed; the work is lining the two up over the primes 2, 3, 5, 7 and 11 and comparing exponents in each column. Leave both answers as products of prime powers, as the question asks — multiplying out hides the structure and invites an arithmetic error at the last step.

The Euclidean algorithm

Q4 asks for gcd(1573, 1144) with every division shown. Factoring both numbers would also work on numbers this size, and that is precisely why the question specifies the algorithm: it runs in a handful of steps on numbers far too large to factor, and it is the engine everything in the next set is built on.

Why it works is worth one sentence in your own notes, because it is a two-line proof from the definition: any common divisor of a pair divides the remainder as well, since r = a − bq, and conversely — so each line has exactly the same set of common divisors as the line above it, and the process must end because the remainders strictly decrease and cannot go below zero.

Q5(a) is the same algorithm on a second pair, and Q5(b) then uses the identity relating a product to its gcd and lcm.

Divide before you multiply: cancelling the gcd into one of the two numbers first keeps every intermediate value small, while forming the full product ab and then dividing is a long multiplication done for nothing.

Bezout's identity and the extended algorithm

Q6 asks for gcd(391, 299) together with integers x and y satisfying 391x + 299y = gcd(391, 299). Producing the pair is the point: it is a certificate that can be checked in one multiplication, and it is what the next set turns into a modular inverse.

Q7 states Bezout's identity in its strong form: the integers expressible as ax + by are exactly the multiples of gcd(a, b). That single sentence answers both parts. For Q7(a), compute gcd(18, 42), ask whether the right-hand side is a multiple of it, and say which direction of the identity you are using — this is a proof of impossibility, so the argument must be that every value of 18x + 42y is divisible by that gcd, which follows directly from the definition of a common divisor.

For Q7(b) the same test passes, so a solution exists and the identity tells you how to build one: find a combination giving the gcd — by inspection here, since the numbers are small, or by the extended algorithm — and then scale the whole equation by the factor that turns the gcd into the required right-hand side. One solution is all that is asked; do not hunt for the general family.

The synthesis question

Q8 runs the whole set in two parts. Part (a) is Q4 and Q6 on one pair: the Euclidean algorithm for gcd(1309, 1001), then back-substitution to write it as 1309x + 1001y, then the one-line check.

Part (b) supplies the prime factorisation of 1001 and asks you to use the gcd to factor 1309. The gcd is a common divisor, so it comes out of 1309 as a factor; divide and decide whether what remains is prime, using the stopping rule from Q3(a) on a number now small enough to make that quick. Then the lcm follows from the same identity as in Q5(b), or by taking the larger exponent on each prime once both factorisations are written over the same primes — and the two routes agreeing is the check that ends the sheet.

Preview all 4 pages

Click any page to open the full PDF.

Getting the most out of it

Quote the definition before you compute

b | a means a = bk for some integer k; gcd is the largest positive common divisor. Most questions in this set are one substitution away from their definition, and the parts that ask "why" want the definition written out, not a number.

Keep every line of the algorithm

The Euclidean algorithm is run once and used twice — once forwards for the gcd, once backwards for the Bezout coefficients. Number your lines as you go. Recomputing them in Q6 and Q8 because they were scribbled over is the commonest waste of time on this sheet.

Check a certificate, do not admire it

Any claimed x and y can be verified in one multiplication, and any claimed factorisation can be verified by multiplying it back. These are the rare questions whose answers check themselves — use that on every one of them.

Watch the range of the remainder

0 ≤ r < b is not decoration. A negative dividend, a leftover below zero after regrouping, and a remainder left larger than the divisor are three versions of the same error, and each one turns a correct calculation into a wrong answer.

Work over one common list of primes

When two numbers are compared through their factorisations, write both over the same primes, giving an absent prime the exponent 0. Lined up in columns, gcd, lcm and the divisor count are all read off the same table instead of being recomputed from scratch.

Common questions