1b Lecture with solutions

Analog clocks present ambiguity in time readings; for example, 11:00 can be understood as either 11 o'clock in the morning or 23:00 in the evening.
Both 11 and 23 yield the same remainder (11) when divided by 12. This presents a practical application of modular arithmetic, illustrating the concept of congruences.

Definition: For two integers, ( a ) and ( b ), and a positive integer ( m ), ( a ) is considered congruent to ( b ) modulo ( m ) if both integers yield the same remainder when divided by ( m ). This relationship is denoted as:
[ a \equiv b \ (mod \ m) ]
The symbol “≡” is pronounced as “is congruent to”, and ( m ) is referred to as the modulus.
Examples:
- ( 23 \equiv 11 \ (mod \ 12) )
- ( 13 \equiv 33 \ (mod \ 10) )
- ( 21 \equiv 0 \ (mod \ 7) )

The congruence can be expressed mathematically as:
[ a \equiv b \ (mod \ m) \Leftrightarrow m | (a - b) \ \Leftrightarrow \exists k \in \mathbb{Z} \text{ such that } a - b = k imes m ]

Reflexivity: ( a \equiv a \ (mod \ m) )
Symmetry: If ( a \equiv b \ (mod \ m) ), then ( b \equiv a \ (mod \ m) )
Transitivity: If ( a \equiv b \ (mod \ m) ) and ( b \equiv c \ (mod \ m) ), then ( a \equiv c \ (mod \ m) )
Addition Property: If ( a \equiv A \ (mod \ m) ) and ( b \equiv B \ (mod \ m) ), then ( a + b \equiv A + B \ (mod \ m) )
Subtraction Property: If ( a \equiv A \ (mod \ m) ) and ( b \equiv B \ (mod \ m) ), then ( a - b \equiv A - B \ (mod \ m) )
Multiplication Property: If ( a \equiv A \ (mod \ m) ) and ( b \equiv B \ (mod \ m) ), then ( a \cdot b \equiv A \cdot B \ (mod \ m) )

To solve congruences of the form ( f(x) \equiv c \ (mod \ m) ):
- Enumerate all integer values ( x ) from ( 0 ) to ( m-1 )
- Compute ( f(x) ) for each value and compare to ( c )

Solve ( 23 \equiv 2x - 3 \ (mod \ 6) ):
- Transform to ( 26 \equiv 2x \ (mod \ 6) )
- Solve yields solutions: ( x \equiv 1, 4 \ (mod \ 6) )
Solve ( x^2 \equiv 1 \ (mod \ 4) ):
- Yields solutions: ( x \equiv 1, 3 \ (mod \ 4) )
For ( x^2 \equiv 2 \ (mod \ 4) ):
- No solutions exist.

A linear integer equation is an equation of the form:
[ ax + by = c ] where ( a, b, ) and ( c ) are integers, and ( x, y ) are unknown integers.

Solve the equation ( 11x - 98y = 1 ): A known solution is ( x = 9, y = 1 )
For the equation ( 8x + 2y = 4 ): A solution is ( x = 1, y = -2 )
Some equations, like ( 8x + 2y = 5 ), have no integer solutions because the gcd does not divide ( c ).

A linear integer equation ( ax + by = c ) has solutions if and only if ( ext{gcd}(a, b) | c ).
If a solution exists, it can be expressed in the format:
[ x = x_0 + \frac{b}{\text{gcd}(a, b)}n, \ y = y_0 - \frac{a}{\text{gcd}(a, b)}n \quad \text{for } n \in \mathbb{Z} ]

The Extended Euclidean Algorithm provides a structured way to find integer solutions to equations of the form:
[ ax + by = r ]
For each row generated in the algorithm, integer solutions can be derived.

Solve ( 7x + 9y = 1 ): ( \text{gcd}(7, 9) = 1 )
- Found solution: ( x = 4, y = -3 )
Solve ( 42x - 18y = 17 ): No solutions exist since gcd does not divide 17.
Solve ( 38x + 34y = 200 ): Solutions derived and general solutions expressed.

Congruences establish relationships indicating equal remainders after division by a modulus.
The validity of linear integer equations relies on gcd divisibility. Solutions can be systematically obtained using methods like the Extended Euclidean Algorithm.