Linear Congruences and GCD Problems

This video tutorial explains linear congruences, their definition, and conditions for solvability. It provides three example problems to illustrate the process of solving linear congruences, including the use of the Euclidean algorithm. The tutorial emphasizes the importance of the greatest common divisor (GCD) in determining solvability and finding solutions.

What is a linear congruence?

• An equation of the form ax + b = c

• A system of linear equations

• A congruence of the form ax ≡ b (mod n)

• A polynomial equation of degree 2

Under what condition does a linear congruence have a solution?

• When a is greater than b

• When n is a prime number

• When gcd(a, n) divides b

• When a and b are coprime

In the first example, what is the gcd of 9 and 15?

• 1

• 2

• 5

• 3

Why can we cancel the common factor in the congruence 3x ≡ 2 (mod 5)?

• Because 3 divides 2

• Because 5 is a prime number

• Because 3 is a prime number

• Because gcd(3, 5) = 1

What is the first solution for x in the congruence 3x ≡ 2 (mod 5)?

• 0

• 1

• 3

• 4

How many incongruent solutions does the congruence 9x ≡ 6 (mod 15) have?

• 3

• 1

• 2

• 4

What is the value of x when t = 1 in the solution of 9x ≡ 6 (mod 15)?

• 19

• 14

• 9

• 4

What is the gcd of 10 and 45 in the second example problem?

• 15

• 5

• 10

• 1

What is the first solution for x in the congruence 10x ≡ 15 (mod 45)?

• 3

• 9

• 6

• 12

How many incongruent solutions does the congruence 10x ≡ 15 (mod 45) have?

• 3

• 5

• 4

• 6