Exercises on congrueces

Exercise 1. Find the solutions for the linear congruence

6x ≡ 4 (mod 10)

Exercise 2. Find the solutions (if there exist) of the following congruences:

  1. 3x ≡ 5   mod 4

  2. 3x ≡ 9   mod 6

  3. 4x ≡ 7   mod 9

  4. 6x ≡ 8   mod 6

Exercise 3. Find the coefficient a and b of a linear congruence of the form

ax ≡ b (mod 319)

that admits exactly 11 non-congruent solutions modulo 319. Once done, determine all solutions.

Exercise 4. Examine if the following system admits solutions

x ≡ 7   mod 9
x ≡ 3   mod 5

and if so, determine them.

Exercise 5. Solve the following system of congruences

1025x ≡ 5312065   mod 8
36x ≡ 322   mod 5
4x ≡ 7   mod 3

Exercise 6. Specify under which condition the system x ≡ a mod n, x ≡ b mod m is solvable without assuming that (n,m) =1.

Exercise 7. If from a candy bag we candies two by two, three by three, four by four, and five by five in the bag there will be always one candy left. If we draw candies seven by seven non is left. Determine the minimum number of candies that could be found in the bag.

Exercise 8. Solve the congruence

4x ≡ 3 mod 385

Solutions

  1. gcd(6,4) = 2, so the congruence has two solutions. We can notice easilty that one is x = 4. The other will be x1 = 4 + 10/2 = 9.

    Are these the only solutions? No. In fact, any integer which is congruent to either 4 or 9 mod 10 is also a solution. You should check this for yourself now. So any integer of the form 4 + 10k or of the form 9 + 10k where k ∈ Z is a solution to the given linear congruence. The above linear congruence has infinitely many integer solutions. Whenever a linear congruence has any solutions, it has infinitely many. The solutions fall into congruence classes, and there are only a finite number of congruence classes that solve the congruence. In this case [4]10 and [9]10.

    1. (3,5) = 1, so there exists a unique solution, which is x = 3.

    2. gcd(3,6) = 3|9. Then there are 3 solutions non congruent mod 6.

      3x ≡ 9   mod 6. A solution is x0 = 3.

      x1 = 3 + 6/3 = 5, and x2 = 3 + 2 · 6/3 = 7. Other non congruent solutions are 1,5,7.

    3. (4,9) = 1, so there's only one solution x = 4.

    4. (6,9) = 3 ∤ 8 i.e. not solvable.

  3. Such a congruence is for example 11x ≡ 0 (mod 319), d=(11,319) = 11. All solutions are of the form x0 + h(n/d), h ∈ ℤ, hence all solutions are h ⋅ 29. All the non-congruent solutions are

    k ⋅ 29,   k= 0, ...,10

  4. Write the fist congruence as x = 7 + 9h and substitute in the 2nd to get 7 + 9h ≡ 3 mod 5 which is equal to 9h ≡ −4 (mod 5). Since −4 ≡ 1 mod 5 and 9 ≡ 4 mod 5, we can rewrite as h ≡ 4 (mod 5) which we can write as h = 4 + 5k which by replacing in the original x equation yields to the solution x = 43 + 45k or x ≡ 43 (mod 45). We could also represent the solutions as the class [43]45.

  5. 1025 ≡ 1 (mod 8), 36 ≡ 1 (mod 5), and 4 ≡ 1 (mod 3). So the original system is equivalent to the system x ≡ 5312065 mod 8 ; x ≡ 322 mod 5; x ≡ 7 mod 3. By noting that 5312065 ≡ 1 (mod 8), 322 ≡ 2 (mod 5) and 7 ≡ 1 (mod 3) so the original system is now x ≡ 1 (mod 8), x ≡ 2 (mod 5), x ≡ 1 (mod 3).

    x = 1 + 3k -> Replace in the second 

1 + 3k ≡ 2 mod 5

3k ≡ 1 mod 5

k ≡ 2 mod 5

so k=2+5j, and now x = 1 + 3(2+5j), x = 7+15j

Replace in x = 1 mod 8

7+15j = 1 + 8l

15j = -6 +8l

15j ≡ 2 mod 8

15 ≡ -1 mod 8

-j ≡ 2 mod 8

j ≡ -2 mod 8

j ≡ 6 (mod 8) 

x = 7 + 15(6+8t) = 7 + 90 + 120t = 97 + 120t

  6. We write the system as

    x = a + nk
    x = b + mh

    subtract the 2nd from the 1st to yield

    0 = a − b +nk − mh

    the solvability is equivalent to the existence of an integer k such that a − b + nk ≡ 0 (mod m) then

    −nk ≡ a − b (mod m)

    we know the congruence ax ≡ b (mod n), admits solutions if and only if d = gcd(n, m) | a-b.

    Suppose you have two solutions x1 and x2 since x1 ≡ a ≡ x2 mod n and x1 ≡ b ≡ x2 mod m we have x1 ≡ x2 mod n and x1 ≡ x2 mod m. This means that n∣(x1 − x2) and m∣(x1−x2). Therefore x1 − x2 is a multiple of both n and m. So, it is a multiple of the least common multiple of n and m by the very definition of that notion. Hence x1 − x2 ≡ 0 mod lcm(n,m), that is x1 ≡ x2 modulo lcm(n,m), as we want.

  7. We can set the following system of equations x = n ⋅ 2 + 1, x = n ⋅ 3 + 1, x = n ⋅ 4 + 1, x = n ⋅ 5 + 1, x = n ⋅ 6 + 1, x = n ⋅ 7, which is equivalent to the following system of congruences

    x ≡ 1   mod 2
    x ≡ 1   mod 3
    x ≡ 1   mod 4
    x ≡ 1   mod 5
    x ≡ 1   mod 6
    x ≡ 0   mod 7

    noting thta x ≡ 1 mod 2 and x ≡ 1 mod 4 <=> x ≡ 1 mod 4 and x ≡ 1 mod 3 and x ≡ 1 mod 6 <=> x ≡ 1 mod 6, the system is equivalent to

    x ≡ 1   mod 3
    x ≡ 1   mod 4
    x ≡ 1   mod 5
    x ≡ 0   mod 7

    on which we can apply CRT. Hence we have to solve the system

    140x̄ ≡ 1 mod 3
    105 x̄ ≡ 1 mod 4
    84x̄ ≡ 1 mod 5
    60x̄ ≡ 0 mod 7

    The first has solution 2, the second 1, the third 4 and the fourth 0. Then x̄ = 140 * 2 + 105 + 84 *4 + 0 = 721. So the solution of the system x = 721 mod 420 thus x = 301.

  8. 385 = 5 ⋅ 7 ⋅ 11. This linear congruence is equivalent to the system of congruence

    4x ≡ 3 mod 5
    4x ≡ 3 mod 7
    4x ≡ 3 mod 11

  9. Exercise 4.28. (Days of the week) Congruences have long been used implicitly to compute dates. As an example, let us determine what day of the week August 18 in the year 2020 will be. To keep track of the days we assign the integers 0, 1, 2, ..., 6 as labels for the days of the week, say Sunday = 0, Monday = 1, ..., Saturday = 6. Suppose that we reckon from July 12, 1987, which was a Sunday. All we have to do is count the number of days from July 12, 1987 to August 18, 2020. Allowing for leap years, this number is 8629. Now 12091 ≡ 2 (mod 7) and 2 is the label for Tuesday. We conclude that August 18, 2020 will be a Tuesday.

«Chinese remainder theorem Index Euclidean Algorithm »