Call Now: (800) 537-1660
 Home    Why?     Free Solver   Testimonials    FAQs    Product    Contact

May 24th

May 24th

# Number Theory and Cryptography

Theorem 1.4 If c|a and c|b, then c|(ax + by) for any integers x and y.

Proof: We have a = cq1 and b = cq2, so ax + by = acq1 + bcq2 = c(aq1 + bq2). This gives
the result.

A number of the form ax+by is called a linear combination of a and b . So this result simply
states that if a number divides two numbers a and b, it divides any linear combination of
them. Note that in line with our previous statement , these letters refer to integers only.

For example, if x and y are any integers, 7|(21x − 35y). This is because 7|21 and 7|35.

The Greatest Common Divisor .
When we reduce a fraction to lowest terms , we find a divisor of the numerator and the
denominator (a common divisor) and cancel it. Thus we have the familiar computation

To reduce the fraction a/b to lowest terms, it would be necessary to find the greatest common
divisor of a and b. This is simply called gcd(a, b). This computation is very cumbersome if
the numerator and denominator are large. For example, how would you reduce the fraction
28, 841/33, 043 to lowest terms? The method we now show handles this problem very quickly,
and was first d one by Euclid . The technique is called the Euclidean Algorithm.

Lemma 1.5 Let a = bq + r. Then any divisor of both a and b is also a divisor of b and r.
Conversely, any divisor of both b and r is also a divisor of a and b. Thus gcd(a, b) = gcd(b, r).

Proof: First, suppose d|a and d|b. Then since r = a − bq, we have d|r since r is a linear
combination of a and b. Thus d|b and d|r.

Conversely, if d|b and d|r, then since a = bq + r is a linear combination of b and r, we see
that d|a and so d|a and d|b. This proves the result.

In words, gcd(a, b) can be found by finding the remainder r when a is divided by b and
computing gcd(b, r). We then use the same result to simplify gcd(b, r), and continue until
we find the answer. Let's use this method to find gcd(75, 55). (Of course this can immediately
be done by most students, but let's illustrate the method.) Dividing, we have

These equations show that

gcd(75, 55) = gcd(55, 20) = gcd(20, 15) = gcd(15,5) = gcd(5, 0) = 5

using the above theorem successively, and the fact that gcd(a, 0) = a when a > 0. This is
a general technique. Instead of finding gcd(a, b) we find the remainder r when a is divided
by b and find gcd(b, r). We keep repeating the process until the remainder is 0, and then
the last non- zero remainder is the required gcd. As noted above, this technique is called
the Euclidean Algorithm. For simplicity, we have as sumed that a and b are positive in
this statement
of the Euclidean algorithm, and we will often make this assumption in what
follows.

We can now reduce 28, 841/33, 043 to lowest terms! The following table systematically gives
the numerator, denominator, quotient and remainders in the Euclidean Algorithm.

 Numerator Denominator Quotient Remainder

The gcd is 191. Note that in each line, the numbers move over one to the left, and the
quotients are ignored. Finally, we reduce to lowest terms:

The Euclidean Algorithm computation will be done automatically in the lab, using the Excel

Many facts about number theory were simply told to us at an early age, and so we take
them for granted. For example, suppose you know that 5|7x. Does it follow that 5|x? We
were taught to think somewhat as follows:

7x/5 is a whole number, and so there must be cancelations. There is no cancelation
of 5 with 7, so all the cancelations are with x, and so 5| x.

Here, the result is true, but the reasoning is suspect. Here is a real proof :

We are given that 5|7x. Also 5|5. Therefore by the linear combination theorem,
5|(3 ٠ 7x − 4x ٠ 5), or using algebra, 5|x.

Query: Suppose we are given that 6|15x. Can we say that 6| x? What can we say about
divisors of x?

The correct proof given above is based on the simple observation that 1 = 7 ٠ 3 − 5٠ 4. We
were able to express 1 as a linear combination of 5 and 7. Here gcd(5, 7) = 1. We shall now
show that if d = gcd(a, b), then d is a linear combination of a and b.

Theorem 1.6 Let d = gcd(a, b). Then there are integers x and y such that

d = ax + by

Remark: The proof will show how to compute x and y. In the lab, the spreadsheet GCD
also computes the values of x and y .

Proof: If we divide a by b to get a = bq + r, we know that d = gcd(b, r), and we note that
r = a − qb = a ٠ 1 + b(−q), a linear combination of a and b. If we continue the Euclidean
Algorithm, we divide again we divide b by r to nd b = rq1+r1. Then the second remainder
r1 = b − rq1 is also a linear combination of a and b since b and r are. Continuing in this
way, we can show that every remainder is a linear combination of a and b. In particular d
is, since it is the last non-zero remainder.

We illustrate this technique with a simple numerical example.

Example 1.7 Find d = gcd(92, 17) and express it as a linear combination of 92 and 17.

Method: The Euclidean algorithm gives

92 = 17٠ 5 + 7
17 = 7٠ 2 + 3
7 = 3 ٠ 2 + 1

Starting from the top, we get

We underline the original numbers to keep track of them. Now use the second equation to
get

Finally, using the last equation and the previous expressions for the remainders 7 and 3, we
obtain

Theorem 1.6 has an interesting corollary. We have defined gcd(a, b) as the greatest common
divisor of a and b. Thus, if d|a and d|b, then d ≤ gcd(a, b). We can now state more.

Corollary 1.8 If d|a and d|b, then d|gcd(a, b)

For a proof, we can write gcd(a, b) = xa + yb, so d|gcd(a, b), since gcd(a, b) is a linear
combination of a and b. In words, any common divisor of a and b is also a divisor of their
gcd.

For example, if two numbers have gcd 6, then 4 cannot divide both of these numbers.

Corollary 1.9 gcd(a, b) = 1 if and only if 1 is a linear combination of a and b.

Proof: Theorem 1.6 shows that if gcd(a, b) = 1, then 1 is a linear combination of a and
b. Conversely, if 1 is a linear combination of a and b then any divisor of a and b must also
divide 1, and so must equal 1. So gcd(a, b) = 1.

Theorem 1.10 Let gcd(a, b) = 1 and a|bn. Then a|n.

Proof: The proof parallels the example above, when 5|7x. Since gcd(a, b) = 1, we have
1 = ax + by for some integers x and y. Multiply by n to get n = axn + bny. Now since a|a
and a|bn, we have a|n since n is a linear combination of a and bn.

Definition 1.11 If gcd(a, b) = 1, we say that a and b are relatively prime.
Thus, we can restate the Theorem 1.10. If a and b are relatively prime, and a|bn, then a|n.
A useful alternative is the following result.

Corollary 1.12 If a and b are relatively prime, a|n and b|n, then ab|n.

Proof: Since a|n, we have n = aq for some q. Thus b|aq. Since a and b are relatively prime,
b|q by the above result, and so q = bq1 for some q1. Therefore n = aq = abq1. This shows
that ab|n.

If we \divide out" the gcd of two numbers, the resulting quotients are relatively prime.

Theorem 1.13 Let d = gcd(a, b). Then a/d and b/d are relatively prime.

Proof: Write d = xa + yb. Divide by d to get 1 = x(a/d) + y(a/d). This shows that a/d
and b/d are relatively prime by Corrolary 1.9.

Theorem 1.14 gcd(xa, xb) = x gcd(a, b) for any x > 0.

Proof: Let d = gcd(a, b). Then since d|a and d|b, we have xd|xa and xd|xb, so xd is a
common divisor of xa and xb. Therefore

gcd(xa, xb) ≥ xd

On the other hand, we know that x is a common divisor of xa and xb. Therefore by
Corollary 1.8, gcd(xa, xb) is a multiple of x, say xD. Thus xD|xa and xD|xb, and therefore
D|a and D|b. Since D is a common divisor of a and b, we must have D ≤ d. Thus,

gcd(xa, xb) = xD ≤ xd:

These two inequalities prove the result.

We can give a useful test to decide whether two numbers a and b are relatively prime. Using
Definition 1.11 and Theorem 1.6, we know that if two numbers are relatively prime, then 1
is a linear combination of them. The following theorem is a valid converse.

Theorem 1.15 Let ax + by = 1 for some integers x and y. Then a and b are relatively
prime.

Proof: Let d be a common divisor of a and b. Then, by Theorem 1.4, d divides any linear
combination of a and b. Therefore d|1 and so d = 1 since the only positive divisor of 1 is 1.
Therefore gcd(a, b) = 1 and so a and b are relatively prime.

For example, all that's required to show that 5 and 7 are relatively prime is to observe that
3 ٠ 7 − 4 ٠ 5 = 1.

Here's an example to use some of these results. It will be used in the next section.

Example 1.16 Given: gcd(a, b) = 1. Prove: gcd(a + b, a − b) = 1 or 2.

Method: Let c = a+b and d = a−b. Add to eliminate b . This gives c+d = 2a. Similarly,
by subtracting , we get c−d = 2b. Now let f be any common divisor of c and d. Thus f|c and
f|d. Therefore, by the above two equations, we find f|2a and f|2b. Therefore f|gcd(2a, 2b).
But by Theorem 1.14, gcd(2a, 2b) = 2gcd(a, b) = 2. Therefore, f|2 and so f = 1 or f = 2.

 Prev Next

Home    Why Algebra Buster?    Guarantee    Testimonials    Ordering    FAQ    About Us
What's new?    Resources    Animated demo    Algebra lessons    Bibliography of     textbooks