We present an ancient theorem on the representation of positive integers as products of prime numbers. The consequences of this theorem are important for a host of reasons.
A factor of a number is called a divisor. Thus, 10 has the divisors 1, 2, 5, and 10. The divisors of n other than n are called proper divisors. The proper divisors of 10 are, therefore, 1, 2, and 5, while its divisors are 1, 2, 5, and 10. A divisor of n is said to divide n. Thus, 5 divides 10, while 7 does not divide 10. The symbol for “divides” is a vertical line. When a divides b, we write a | b. Whenever a divides b, observe that b is a multiple of a, that is, b = ka, for some integer k. Thus, 5 | 10, while 10 = 2 × 5. In fact, this is an “if and only if” statement:
In symbols, we have, using the two-way implication arrow,
Here is a nice way to think about (4.1). Even though 20 divides 100, one may write 100 = 4 × 25, preventing us from seeing the 20. On the other hand, we can write 100 = 5 × 20, thereby showing us the divisor (or factor) 20.
Here are a few laws of divisibility. As is our practice throughout the text, all letters represent integers (whole numbers) unless otherwise stated:
We shall prove Law 1 and leave the rest for the reader. Using (4.1), we have b = ka and c = jb. Then we obtain the following chain of equations: c = jb = jka = (jk)a = ha, where h = jk. Equating the first and last parts of this super equation, we get c = ha. Then by (4.1), a | c.
The expression mr + ns in Law 5 is called a linear combination of r and s, since it is the sum of multiples of r and s. So 530 is a linear combination of 100 and 10, namely, 5 × 100 + 3 × 10. This concept can be extended to more than two numbers. mr + ns + pt is a linear combination of r, s, and t. So 534 is a linear combination of 100, 10, and 1, namely, 5 × 100 + 3 × 10 + 4 × 1. By contrast, expressions such as 6r2 + 10s3, 2rs, , are nonlinear.
Let’s prove by induction that 8 | (25n + 7). The base case, n = 1, is obvious since 8 | 32. Now, we assume that 8 | (25k + 7) and we must show that 8 | (25k+1 + 7). We have, using (4.1), that 25k + 7 = 8j. Then 25k = 8j − 7. Multiplying by 25 yields 25k+1 = 25(8j − 7) = 200j − 175. Adding 7 to both sides yields 25k+1 + 7 = 200j − 168 = 8(25j − 21). After eliminating the middle member of this equation, we have 25k+1 + 7 = 8(25j − 21), showing that 8 is indeed a divisor of 25k+1 + 7, and the clever proof is over.
Imagine how difficult it would be to compute 25837 + 7 in order to show that it is a multiple of 8.
Given a and b, we call d the greatest common divisor of a and b, denoted gcd(a,b), if:
If gcd(a,b) = 1, we say that a and b are relatively prime, that is, they have no common divisor other than 1. Note from the preceding example that
where min{a,b} denotes the smaller of a and b. Furthermore, we will have equality if and only if a | b (as in our second example, gcd(15,45) = 15).
It is important to note that gcd(a,b) = d if and only if a = rd and b = sd, where r and s are relatively prime. To illustrate this, observe that 15 = 3 × 5 and 35 = 7 × 5. Since 3 and 7 are relatively prime, we see that gcd(15,35) = 5. Note, also, that when we reduce a fraction to lowest terms, we cancel the gcd of the numerator and denominator, leaving a new pair of integers with a gcd of 1. In the notation of the first sentence of this paragraph, we have . The last fraction is reduced to lowest terms since, by assumption, gcd(r,s) = 1. So gcd(a,b) is the greatest number that we can cancel when we reduce . Furthermore, gcd(a,b) = d is the greatest number that we can factor out of the expression a + b, that is, a + b = d(r + s). For example, 100 + 175 = 25(4 + 7). Since 4 and 7 are relatively prime, we can’t factor further.
Before we present an algorithm for finding gcd(a,b), here is the way we write the division of b by the positive number a in a way that avoids fractions. (We wish to avoid statements such as .)
If a = 4 and b = 35, for example, then q = 8 and r = 3. We have 35 = 8 × 4 + 3. In words, this says that 35 divided by 8 is 4 and the remainder is 3. Note that 3 < 4. This is why r < a. Since we are dividing by a, the remainder must be less than a, or we would get a larger quotient. If one claims that 20 ÷ 6 = 2 with a remainder of 8, we would protest since 6 goes into 8 one time (with a remainder of 2), implying that 20 ÷ 6 = 3 with a remainder of 2. Note, furthermore, that r = 0 if and only if a | b or, equivalently, r = 0 if and only b is a multiple of a. In this case, b = qa, or equivalently, .
Note that if d is a common divisor of a and b, then given any number n, it follows that d must also divide b − na, by Law 5 above. For instance, d = 5 is a common divisor of a = 15 and b = 100. Then 5 is also a common divisor of 15 and 85, which is 100 − 15 or b − 1a. It is also a common divisor of 15 and 70, which is 100 − 2 × 15 or b − 2a, etc.
Moreover, if d | a and d | (b − na), then d | b, since b = na + (b − na). In other words, d is a common divisor of a and b if and only if d is a common divisor of a and b − na for any n. Stated formally,
This last calculation will be expedited by making b − na as small as possible using the division algorithm. This is done by letting n = q, where q is the quotient when b is divided by a. Then b − qa will be the remainder r in the equation b = qa + r. It then follows that b − qa < a. The point of all this is that gcd(a,b) = gcd(a, b − qa).
We conclude from the next to the last equation, 8 = 1 × 6 + 2, that d = 2.
The final “division” equation will always have a zero remainder, since the remainders form a strictly decreasing sequence of nonnegative numbers. The remainder in the second to the last equation in the example above yields the gcd, 2, of 30 and 292. In general, to find d = gcd(a,b), we will obtain a sequence of equations of the form
and rk = d = gcd(a,b). Note that r1 > r2 > r3 > … > rk = d.
The Euclidean algorithm yields an interesting fact, which we will find useful. The second to the last equation can be written (recalling that d = rk)
From the equation before that one, we get rk−1 = rk−3 − qk−1rk−2, which allows us to rewrite (4.2) as d = rk−2 − qk(rk−3 − qk−1rk−2) = −qkrk−3 + rk−2 + qkqk−1rk−2 or
Using the equation, rk−4 = qk−2rk−3 + rk−2, we can replace rk−2 in (4.3) by rk−4 − qk−2rk−3, obtaining
where A and B are expressions involving qk−2, qk−1, and qk.
What is the point? Moving up the ladder using the above procedure, we will finally obtain d = ma + nb, where m and n are integers! In other words, gcd(a,b) is a linear combination of a and b.
In fact, d is the smallest positive number expressible as a linear combination of a and b. Here’s why. Assume to the contrary that 0 < c < d and c = ra + sb. Now, d | (ra + sb), so d | c, which is absurd.
Note in particular that if d = gcd(a,b) = 1, that is, if a and b are relatively prime, then there are integers m and n such that ma + nb = 1.
The second equation implies that 6 = 30 − 24. By the first equation, 24 = 84 − 2 × 30. Substituting the right side of this equation for 24 in 6 = 30 − 24 yields 6 = 30 − (84 − 2 × 30) = 3 × 30 − 1 × 84.
The following theorem will have major consequences. Even though it will seem obvious, we will prove it using a fact we proved earlier in this chapter.
Note that this theorem is true only when p is prime. Consider the composite number 10 that divides 4 × 5, without dividing 4 or 5. Observe, furthermore, that the theorem can be extended to include larger products. Thus, for example, if p is a prime number and p | abc, then either p | a, p | b, or p | c. In other words, if a prime divides a product of integers, then it must divide at least one of them.
Here’s another theorem whose proof is similar to the proof of the preceding one.
Let us now prove an interesting theorem about the Fibonacci numbers.
We have made use, in the above proof, of Law 5, which says that a | r and a | s ⇒ a | (mr + ns). With m = 1 and n = −1, this says that a | r and a | s ⇒ a | (r − s). Here’s a nice theorem.
then their sum, , is not an integer.
An equation such as 2x + 3y = 7 has infinitely many solutions when x and y are real numbers. In fact, the solutions are the coordinates of any point on the straight line described by that equation. In this text, we are concerned only with integer solutions. You might guess that the pair of values x = 2 and y = 1 supplies such a solution. Are there others? Is there a method for finding integer solutions for equations such as this one?
An equation of the form ax + by = c, where a, b, and c are given integers and the solution we seek consists of a pair of integers, is called a Diophantine equation, in honor of the ancient Greek number theorist, Diophantus. Before we see how to solve a Diophantine equation, note that not every equation of this kind can be solved. Consider the Diophantine equation 2x + 6y = 7. Since 2 divides the left side, we would require that 2 | 7, which is not the case. Thus, there is no solution in integers. The following theorem should be obvious, in light of this example, so we shall leave the proof as an exercise at the end of the chapter.
On the other hand, if gcd(a,b) | c, then the equation ax + by = c has a solution. In fact, it has infinitely many solutions. Let’s state this as a theorem.
Let the pair of integers x0 and y0 (read “x naught” and “y naught”) be a solution of ax + by = c. Then for any integer t, let
We claim that the pair of integers x and y yield another solution of ax + by = c. To prove this, we have a(x0 + bt) + b(y0 − at) = ax0 + abt + by0 − bat = ax0 + by0 = c, since x0 and y0 satisfy the original equation. So we have infinitely many solutions, since any t will do.
In fact, all solutions to ax + by = c are of the form x = x0 + bt and y = y0 − at. To prove this, let the pair (x', y') be a solution of ax + by = c, where gcd(a,b) = 1. (Recall that this is doable when gcd(a,b) | c. Simply divide by gcd(a,b).) Then ax' + by' = c. Now, the pair (x0, y0) is also a solution. Subtracting ax0 + by0 = c yields a(x' − x0) + b(y' − y0) = 0, from which we have a(x' − x0) = −b(y' − y0). Since b divides the right side of this equation, it follows that b divides the left side, that is, b | a(x' − x0). Furthermore, since gcd(a,b) = 1, we have b | (x' − x0). Then x' − x0 = bt, for some integer t. Inserting this into a(x' − x0) = −b(y' − y0) yields abt = −b(y' − y0), which becomes at = −(y' − y0). A drop of algebra then gives us x' = x0 + bt and y' = y0 − at.
If a, b, and c are positive, there will be at most finitely many solutions where x and y are positive. This is because the line ax + by = c will intercept the positive x and y axes, implying that only a finite segment of the line will be in Quadrant I. As a simple example, consider the Diophantine equation x + y = 2. The only solution where x and y are positive is x = y = 1.
Positive solutions require 14 − 3t > 0 and 2t − 1 > 0, or . Then we have the permissible values t = 1, 2, 3, and 4, yielding the solutions obtained earlier.
Euler posed and solved the following problem involving a pair of Diophantine equations. A group of 30 men, women, and children spent a total of 50 dollars at an inn that charged men 3 dollars, women 2 dollars, and children 1 dollar. How many people were there in each class? Denoting the number of men, women, and children by x, y, and z, we have the two Diophantine equations
By subtraction, we obtain 2x + y = 20. Then y = 20 − 2x. Clearly, x can assume any of the values 1, 2, 3, …, 9, while y assumes the corresponding values 18, 16, 14, …, 2. The corresponding z values, 11, 12, 13, and 19, are found using z = 30 − x − y.
Given integers a and b, the smallest positive integer, c, such that a | c and b | c is called their least common multiple and is denoted lcm(a,b). Note that c is indeed a common multiple of a and b, that is, c = ra and c = sb, where gcd(r,s) = 1. If gcd(r,s) = d > 1, then a and b would have a smaller common multiple, . Observe that lcm(a,b) ≥ max{a,b}, where max{a,b}denotes the maximum of a and b. In fact, when a | b, we have lcm(a,b) = max{a,b} = b. On the other hand, we have an upper bound given by lcm(a,b) ≤ ab. Equality occurs when gcd(a,b) = 1. In other words, when a and b are relatively prime, lcm(a,b) = ab.
The lcm, c, of a and b should be familiar to you. It is the lowest common denominator of the (reduced) fractions and . Addition of these fractions proceeds thusly . Of course, when a and b are relatively prime, this becomes , since c = lcm(a,b) = ab.
Given a and b, since gcd(a,b) | a and a | lcm(a,b), it follows that gcd(a,b) | lcm(a,b). Now, here are a few question that illustrate the modus operandi of the number theorist:
For starters, note that the pair G and L answer the first question, that is, gcd(G,L) = G and lcm(G,L) = L, since G | L. Question 2 is harder to answer. Sometimes, the answer is unique and sometimes it isn’t. When G = 4 and L = 8, the only answer is a = 4 and b = 8. On the other hand, when G = 10 and L = 300, we have the four pairs (10, 300), (20, 150), (30, 100), and (50, 60). The third question is left as an exercise.
If we asked several people to factor 100, we would get a number of different answers, such as 2 × 50, 4 × 25, 5 × 20, and 10 × 10. If we stipulated that all the factors must be primes, all respondents would, except for order, give us the same answer, 2 × 2 × 5 × 5, or 22 × 52. This is called the prime decomposition of 100. We present the following important theorem.
In light of this theorem, we see that the primes are the building blocks of the integers. In this sense, they are truly prime, or first among all numbers.
Recall from Chapter 2 that to determine whether a given positive integer n is a prime, it suffices to check whether n is divisible by any of the numbers less than or equal to . By the above example, the observation can now be improved. We have the following remark.
A positive integer n is called semiprime if n = pq where p and q are distinct primes. Thus, 6 = 2 × 3, 10 = 2 × 5, and 14 = 2 × 7 are the first three semiprimes. Here is an interesting theorem about semiprimes.
The condition of the theorem need not be present when n is semiprime as is shown by the fact that the smallest prime divisor, 2, of the semiprime 10 does not exceed . It is not an “if and only if” theorem. The next theorem will be proven using prime decomposition.
The next theorem tells us when a given number is a square, a cube, or, more generally, a power. In other words, when is a given number, n, an mth power? In still other words, when does n equal cm?
The statement a | b has a simple interpretation using prime decomposition. Whenever a prime p occurs in the prime decomposition of a with exponent r, it must occur in the prime decomposition of b with exponent s, where s ≥ r. Thus, 20 | 600, since 20 = 2251, and 600 = 233152. Using this observation, the proof of the next theorem will be easy.
Observe that the above theorem is not valid when a and b are not relatively prime. Consider the fact that 6 and 10 divide 30, while their product, 60, does not. The problem here is that 6 and 10 both contain the factor 2, which 30 also contains, while the product 6 × 10 contains the factor 22, which 30 does not contain.
While odd primes cannot be consecutive, here and there, we find pairs of primes, such as 17 and 19, such that their difference is 2. We call them twin primes. The first few are 3 and 5, 5 and 7, 11 and 13, 17 and 19, and 29 and 31. It is currently not known if there are infinitely many pairs of twin primes. Nevertheless, here is a nice theorem concerning them.
Observe that all positive integers greater than 11 can be written as 12k + r, where k ≥ 1 and r = 0, 1, 2, …, 11. If p is prime, we can write p = 12k + r, but r is now restricted to the values 1, 5, 7, and 11. If r = 3, for example, we have p = 12k + 3 = 3(4k + 1), a contradiction.
The great seventeenth-century number theorist Pierre Fermat (1601–1665) conjectured that is always prime. This is true when n = 0, 1, 2, 3, and 4. In the following century, Euler found that when n = 5, Fermat’s expression is composite, by showing that 641 | 232 + 1. While this is easy to do today with the help of a computer, here is a number theoretic argument.
Let x = 27 = 128 and let y = 5. Then 1 + xy = 1 + 5 × 128 = 641. We also have 1 + xy – y4 = 1 + y(x − y3) = 1 + 5 × 3 = 16 = 24. Finally, 232 + 1 = 24228 + 1 = 24(27)4 + 1 = (1 + xy – y4)x4 + 1 = (1 + xy)x4 + (1 − x4y4) = (1 + xy)x4 + (1 − x2y2)(1 + x2y2) = (1 + xy)[x4 + (1 − xy)(1 + x2y2)] = 641[x4 + (1 − xy)(1 + x2y2)], and we are done. To date, it is not known whether there are any more Fermat primes, that is, primes of the form . The number wasn’t factored until 1971. We denote the nth Fermat number, , by Fn. As of this writing, no Fermat primes have been found beyond F4. Before we leave the topic of Fermat numbers, here is a theorem with a surprising consequence.
It follows that the nth Fermat number, Fn, contains at least one prime divisor that does not divide any of the Fermat numbers, Fm, where m < n. So there are infinitely many primes!
x and x, where x is a nonnegative real number, mean “round down x” and “round up x,” respectively. Thus, , while . Similarly, and . When x is an integer, . Using this notation, here’s an interesting theorem.
All integers can be written mb + r, where 0 ≤ r < b. Assume that the N we are looking for is of the form Mb. Consider all numbers, n, of the form mb + r, where m ≥ M and 0 ≤ r < b. Now, n = mb + r = mb + r × 1 = mb + r(ax − by) = rax + (m − ry)b.
Clearly, m − ry is the problem here. We must show that we can make this number positive. We have the following inequality: m − ry ≥ M − ry ≥ M − (b − 1)y. It suffices, therefore, to choose M so that M > (b − 1)y. Finally, since N = Mb, we can let N = b(b − 1)y.
Note that if gcd(a,b) = d > 1, no N exists, since d | ra + sb, for all r and s.
Let’s obtain the prime decomposition of n!. Now, p is a prime factor of n! if and only if p ≤ n. Call these primes p1, p2, …, pr, and let their exponents be e1, e2, …, er. So .
To determine ei, first find the number of integers up to n containing pi as a factor. This number is . For example, the number of integers up to 65 that contain 3 as a factor is , implying that 321 | 65!. But this number is too small, since numbers such as 9 and 18 contain more than one “3” as a factor. Thus, we must add to the previously obtained 13. In general, we must add to . Returning to the specific example, 65!, since 27 and 54 contains three “3s” as factors, we must add on , obtaining the exponent 21 + 7 + 2 = 30 of 3 in the prime decomposition of 65!. What would happen if we continued this example and divided by the next power of 3, that is, 34 or 81? Since we are rounding down, the answer is “no harm done” since .
In fact, the exponent of 3 in the prime decomposition of 65! may be written as the infinite series . In the spirit of this idea, we have the following.
Recall that we proved in the previous chapter that no nonconstant polynomial f(x) with integer coefficients assumes only prime values when x = 1, 2, 3, …. We prove this using divisibility.
It is easy to verify the algebraic identity . When n = 3, by the way, it tells us how to factor the difference of two cubes:
a fact not as well remembered as the way to factor the difference of two squares. It follows that a − b | an − bn, for n = 1, 2, 3, …. Consider , where the coefficients are integers. We find that
So
Now, since each term on the right contains a factor of the form an − bn and since we know that a − b | an − bn, for n = 1, 2, 3, …, k, we have the proven the following theorem.
Alternatively, we have f(a) − f(b) = K(a − b), where K is an integer. We are ready to prove the following theorem.
An asterisk (*) indicates that the exercise can be developed into a research project.
Greatest Common Divisor
<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>GCD</title>
<script>
var placeref;
function find(){
placeref = document.getElementById("place");
placeref.innerHTML = "";
gcd(parseInt(document.f.numA.value),parseInt(document.f.numB.value));
return false;
}
function gcd(a,b){
var messages;
var holder;
var r;
if (b < a) {
//switch
holder = a;
a = b;
b = holder;
}
messages = placeref.innerHTML;
messages += "<br/> Searching for GCD of "+String(a)+" and "+String(b)+".<br/>";
placeref.innerHTML = messages;
r = b % a;
if (r==0){
messages+= "GCD is " + String(a);
placeref.innerHTML = messages;
return false;
}
else {
return gcd(r,a);
}
}
</script>
</head>
<body>
Enter two numbers <br/>
<form name="f" onsubmit="return find();">
A: <input type="number" name="numA" value=""/>
B: <input type="number" name="numB" value=""/> <br/>
<input type="submit" value="Enter"/>
</form>
<p id="place">
Messages will go here.
</p>
</body>
</html>
Prime Decomposition
<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Primary Decomposition</title>
<script>
var table = []; //each element will be an array of length 2
function produceFactors(n){
var ans = []; //start off with empty array
//notice start with 2, not 1
for (var i=2;i<n;i++){
if ((n%i)==0){
ans.push(i);
}
}
return ans;
}
function onlyprimes(factors){
var ans = [];
for (var i=0;i<factors.length;i++){
if (isPrime(factors[i])){
ans.push(factors[i]);
}
}
return ans;
}
function makeTable(m,facs){
while (facs.length>0){
f = facs[0]; //always using first, that is, 0th element
if ((m % f)>0) {
//f, the ith element of facs does NOT divide m
facs.shift(); //remove this factor
}
else {
m = m / f;
e=1;
//need to see if exponent is more than 1
while (0 == (m%f) ){
m = m /f;
e++;
}
table.push ([f,e]);
facs.shift();
}
}
return;
}
function isPrime(n){
var lim = Math.sqrt(n);
for (var i=2;i<=lim;i++){
if (0 == n % i){
return false;
}
}
return true;
}
function displaydecomp(){
table = []; //reset table to empty array
placeref = document.getElementById("place");
n = parseInt(document.f.num.value);
factors = produceFactors(n);
pfactors = onlyprimes(factors);
makeTable(n, pfactors); // this function will add to table
messages = "The prime decomposition is <br/>";
for (var i=0;i<table.length;i++){
messages+=String(table[i][0])+"<sup>"+String(table[i][1])+"</sup>";
}
placeref.innerHTML = messages;
return false;
}
</script>
</head>
<body>
Enter number to see its prime decomposition:
<form name="f" onSubmit="return displaydecomp();">
<input type="number" name="num" value=""/>
<input type="submit" value="Enter integer"/>
</form>
<div id="place">
Answer will go here.
</div>
</body>
</html>