Exercises - Linear Congruences

  1. Suppose $a_1 \equiv b_1 \pmod{m}$ and $a_2 \equiv b_2 \pmod{m}$. Prove the following:  

    1. $a_1 + a_2 \equiv b_1 + b_2 \pmod{m}$
    2. $a_1 - a_2 \equiv b_1 - b_2 \pmod{m}$
    3. $a_1 a_2 \equiv b_1 b_2 \pmod{m}$
  2. Prove that if $ac \equiv bc \pmod{m}$ and $\gcd(c,m)=1$, then $a \equiv b \pmod{m}$.  

  3. Find all incongruent solutions to the following:  

    1. $7x \equiv 3 \pmod{15}$
    2. $6x \equiv 5 \pmod{15}$
    3. $x^2 \equiv 1 \pmod{8}$
    4. $x^2 \equiv 2 \pmod{7}$
    5. $x^2 \equiv 3 \pmod{7}$
  4. Use congruences to prove the following divisibility tests for 4, 8, 3, 9, and 11 work.

    1. A number is divisible by 4 if its last two digits yield a number divisible by 4
    2. A number is divisible by 8 if its last three digits yield a number divisible by 8
    3. A number is divisible by 3 if the sum of its digits is divisible by 3
    4. A number is divisible by 9 if the sum of its digits is divisible by 9
    5. A number whose digits are given by $d_n ... d_3 d_2 d_1 d_0$ is divisible by 11 if $ d_0 - d_1 + d_2 - d_3 + \cdots + (-1)^n d_n$ is divisible by 11
  5. Solve the following linear congruences

    1. $8x \equiv 6 \pmod{14}$  
    2. $66x \equiv 100 \pmod{121}$  
    3. $21x \equiv 14 \pmod{91}$  
  6. Determine the incongruent solutions, if they exist, for each of the following:

    1. $72x \equiv 47 \pmod{200}$  
    2. $4183x \equiv 5781 \pmod{15087}$  
    3. $1537x \equiv 2863 \pmod{6731}$  

◆ ◆ ◆