Learn – Math circle – Divisibility and Modular arithmetic

Divisibility

Exercises

Problem set

For each of the following, answer if what is given is true or not.

  1. 5 \mid 10
  2. 3 \mid 13
  3. 4 \nmid 15

Problem set

For each of the following, answer if what is given is true or not.

  1. a \mid b\mbox{ and } b \mid c \implies a \mid c
  2. a \mid b \implies am \mid bm
  3. a \mid b\mbox{ and }a \mid c \implies a \mid mb+nc
  4. am \mid bm \implies a \mid b
  5. a \mid b \implies a^2 \mid b^2

Problem set

Find the values of the following.

  1. 129 \bmod 11
  2. -45 \bmod 8
  3. 0 \bmod 91
  4. -1 \bmod 12345

Problem set

Prove the following.

  1. a \mid b\mbox{ and }a\mid c\implies a\mid mb+nc
  2. am \mid bm\mbox{ and }m \ne 0 \implies a\mid b
  3. For a and b such that 0 < a < b, x\mid a\mbox{ and } x\mid b\implies x\mid b\bmod a.
  4. For a and b such that 0 < a < b, x\mid a\mbox{ and } x\mid b\bmod a\implies x\mid b.
  5. (ak+b)\bmod a = b\bmod a
  6. a\bmod m = c\mbox{ and } b\bmod m = d\implies ab \bmod m = cd \bmod m
  7. a\bmod m = k \implies a^2 \bmod m = k^2 \bmod m
  8. a\bmod m = k \implies a^3 \bmod m = k^3 \bmod m

Problem set

For each of the following, answer if what is given is true or not.

  1. a \mid b \implies a \bmod b = 0
  2. (a+1) \mid b \implies b \bmod a = 1
  3. a \bmod m \,\,= \,\, b \bmod m \implies m \mid a-b
  4. m \mid a-b \implies a \bmod m \,\,= \,\, b \bmod m

Problem set

  1. If 0 \le a < 93, find the value of a \bmod 93.
  2. If a is a prime, 0 < b < a and a \bmod b = 0, find the value of b.
  3. If a > 0 and a \bmod 6 \,\,= \,\,a \bmod 8 \,\,= \,\,0, find the smallest possible value of a.
  4. If a > 0 and a \bmod 9 \,\,= \,\,a \bmod 12 \,\,= \,\,a \bmod 15 \,\,= \,\,0, find the smallest possible value of a.
  5. If a > 10 and a \bmod 9 \,\,= \,\,a \bmod 12 \,\,= \,\,a \bmod 15 \,\,= \,\,2, find the smallest possible value of a.
  6. If 63 \bmod a \,\,= \,\,147 \bmod a \,\,= \,\,0, find the biggest possible value of a.

Problem set

If a \bmod 11 = 7, find the values of the following.

  1. a+93 \bmod 11
  2. 93a \bmod 11
  3. 79a \bmod 11
  4. a^2 \bmod 11
  5. a^5 \bmod 11

Problem set

If a \bmod 13 = 7 and b \bmod 13 = 4, find the values of the following.

  1. a+b \bmod 13
  2. 4a+3b \bmod 13
  3. 7a-9b \bmod 13
  4. a^2-b^2 \bmod 13
  5. 5a+3b^2 \bmod 13

GCF

Exercises

Problem set

  1. Prove the theorem: Given two numbers a and b such that 0 < a < b, then \mbox{gcf}(a,b) = \mbox{gcf}(b\bmod a, a).

Problem set

Use Euclid’s algorithm to find GCF of the following pairs of numbers.

  1. 803, 154
  2. 819, 715

Congruences

Exercises

Problem set

For each of the following, give whether the congruence is true or false.

  1. 30 \equiv 60 \pmod {20}
  2. 22 \equiv -10 \pmod 6

Problem set

In each of the following, find two possible values of x, with one of them being the smallest possible non-negative value.

  1. 17 \equiv x \pmod 7
  2. 39 \equiv x \pmod {13}
  3. -11 \equiv x \pmod 8
  4. -1 \equiv x \pmod {11}

Problem set

For m \ge 1, if a \equiv b \pmod m and c \equiv d \pmod m, then prove the following.

  1. a + c \equiv b + d \pmod m
  2. a - c \equiv b - d \pmod m
  3. ac \equiv bd \pmod m
  4. a^2 \equiv b^2 \pmod m
  5. a^3 \equiv b^3 \pmod m
  6. For all positive integers n, a^n \equiv b^n \pmod m
  7. If p(x) = p_nx^n+p_{n-1}x^{n-1}+\cdots+p_1x+p_0, then p(a) \equiv p(b) \pmod m.

Problem set

  1. Ria’s stamp collection consists of 31 stamps for each of some 31 countries. She wants to organize her stamps into sets of 7, and wants to give away how many ever do not fit into her sets. How many stamps would Ria give away?
  2. A school has 19 sections with each section having 23 students. For MATH circle, the school wants to regroup the students so that each group has 8 students. After the regrouping, how many students will be left over?

Problem set

Evaluate the following.

  1. 1000000^{99} \bmod 99
  2. 1000000^{101} \bmod 101
  3. 49\times 99 \times 149 \times 199 \times 249 \times 299 \times 349 \times 399 \bmod 50

Miscellaneous

Exercises

Problem set

    Find four distinct positive integers such that no subset of them adds up to a multiple of 6.
  1. Find five distinct positive integers such that no subset of them adds up to a multiple of 6.
  2. Find six distinct positive integers such that no subset of them adds up to a multiple of 6.