|
These notes are set so that you get to prove the main results
by solving smaller problems that when put together give the big result.
The answers to the problems are in the videos.
You will get the most out of these notes if you do (or try) the problems
before looking at the videos.
Bézout's Theorem and the Euclidean algorithm.$$ \renewcommand{\mod}[1]{\ (\mathop{\rm mod} #1 )} $$ One of our main results in the last week is:Bézout's Theorem (i.e. GCD is linear combination.) Let \(a\) and \(b\) be integers, not both zero. Then there are integers \(x\) and \(y\) such that $$ ax + by = \gcd(a,b). $$ The text on pages 11-13 gives a nice method using a bit of elementary matrix theory along with the Euclidean algorithm which, given \(a\) and \(b\), both finds computes \(\gcd(a,b0\) and gives integers \(x\) and \(y\) such that \( ax+ by = \gcd(a,b)\). Problem: Use the method of the text to find the greastest common divisor of and \(a = 6643\) and \(b= 2873\). (This is a problem from the text.) Solution. One of the consequences of Bézout's Theorem that is important to us is Theorem: Let \(a\) and \(b\) be integers. Then \(a\) and \(b\) are relatively prime (that is \(\gcd(a,b)=1\) ) if and only if there are integers \(x\) and \(y\) such that $$ ax+by = 1. $$ Proof: One direction follows immediately from Bézout's Theorem: if \(\gcd(a,b) =1\) then Bézout tells us that there are integers \(x\) and \(y\) with \(ax+by = 1\). Conversely if there are integers \(x\) and \(y\) with \(ax+by = 1\) let \(d = \gcd(a,b\) with the goal of showing \(d=1\). Since \(d\) divides both \(a\) and \(b\) it divides the integral linear combination \(ax+by=1\). But the only divisors of \(1\) are \(\pm 1\) and \(d\) is positive, therefore \(d=\gcd(a,b) =1\). QED
We are now going to apply this to the theory of congruences of numbers.
If you need to, review the basic properties of
\( a \equiv b \mod n\).
Problem: Solve the congruence $$ 17 x \equiv 1 \mod {132} $$ Solution. |