1b Practice Problems with solutions

Advanced Mathematics BBA & BAIB 2024-2025

Topic 1: Modular Arithmetic Practice Problems

1. Problem Questions

• Congruences

  1. Solve, if possible, the following congruences. If not possible, justify why not.

  • a) 5𝑥 + 1 ≡ 0 (mod 8)

  • b) 6𝑥 ≡ 3 (mod 12)

  • c) 4𝑥 − 3 ≡ 27 (mod 7)

  • d) |5 − 𝑥3| ≡ 4 (mod 5)

  • e) −3𝑥2 ≡ 2𝑥 (mod 6)

  • f) 3𝑥5 + 7𝑥3 ≡ 40 (mod 124)

• Linear Integer Equations2. Solve, if possible, the following linear integer equations. If not possible, justify why not.

  • a) 11𝑥 + 15𝑦 = 31

  • b) 21𝑥 + 15𝑦 = 12

  • c) 24𝑥 + 28𝑦 = 845

  • d) 169𝑥 − 65𝑦 = 91

  • e) 16𝑥 + 44𝑦 = 20

  • f) (*) 12 345 678𝑥 + 87 654 444𝑦 = 12 · 1010

• Modular Arithmetic Property3. Prove the sixth property of modular arithmetic: If 𝑎 ≡ 𝐴 (mod 𝑚) and 𝑏 ≡ 𝐵 (mod 𝑚), then 𝑎 · 𝑏 ≡ 𝐴 · 𝐵 (mod 𝑚).

• ATM Cash Withdrawal4. An ATM has €50 and €10 banknotes, and always outputs more €10 than €50 in any withdrawal. Determine the possible ways to withdraw €360.

• Trucking Refrigerators5. A trucking company has to move 844 refrigerators with trucks that carry either 28 or 34 refrigerators. List possible ways of moving all the refrigerators.

2. Problem Answers

• Congruences

  1. a) Solve: 5𝑥 + 1 ≡ 0 (mod 8)

  • Reduction leads to 5𝑥 ≡ 7 (mod 8).

  • Possible values for 𝑥 modulo 8: 0, 1, 2, 3, 4, 5, 6, 7 yield 𝑥 ≡ 3 (mod 8).

  b) No solutions; multiples of 6 in mod 12 yield remainders of only 0 or 6.

  c) Solve: 4𝑥 − 3 ≡ 27 (mod 7) converts to 4𝑥 ≡ 2 (mod 7) leading to 𝑥 ≡ 4 (mod 7).

  d) Solve |5 − 𝑥3| ≡ 4 (mod 5): values yield 𝑥 ≡ 1, 4 (mod 5).

  e) Rearranging gives −3𝑥2 ≡ 2𝑥 (mod 6): solution is 𝑥 ≡ 0 (mod 6).

  f) The solutions are 𝑥 ≡ 6, 50, 54, 68, 112, 116 (mod 124).

• Linear Integer Equations2. a) gcd(11, 15) = 1; extended Euclidean algorithm gives:

  • Solution for 11𝑥 + 15𝑦 = 31 becomes 𝑥 = -124 + 15𝑛, 𝑦 = 93 - 11𝑛 for all 𝑛.

  b) gcd(21, 15) = 3; apply algorithm for solutions to yield 𝑥 = -8 + 5𝑛, 𝑦 = 12 - 7𝑛.

  c) gcd(24, 28) = 4 which does not divide 845, hence no solutions.

  d) gcd(169, -65) = 13; extended calculations yield the general solution as 𝑥 = 14 - 5𝑛, 𝑦 = 35 - 13𝑛.

  e) gcd(16, 44) = 4; solutions yield 𝑥 = 15 + 11𝑛, 𝑦 = -5 - 4𝑛 for integers.