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.

DIVISORS

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:

• a divides b if and only if b is a multiple of a.

In symbols, we have, using the two-way implication arrow,

(4.1)

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:

1. a | b and b | c ⇒ a | c.
2. a | b and b | a ⇒ a = ±b.
3. a | b and c | d ⇒ ac | bd.
4. a | b ⇒ ac | bc (where c ≠ 0).
5. a | r and a | s ⇒ a | (mr + ns).
6. a | r and a does not divide s ⇒ a does not divide r + s.
7. If a and b are positive integers such that a | b, then a ≤ b.

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 6r² + 10s³, 2rs, , are nonlinear.

Let’s prove by induction that 8 | (25ⁿ + 7). The base case, n = 1, is obvious since 8 | 32. Now, we assume that 8 | (25^k + 7) and we must show that 8 | (25^k+1 + 7). We have, using (4.1), that 25^k + 7 = 8j. Then 25^k = 8j − 7. Multiplying by 25 yields 25^k+1 = 25(8j − 7) = 200j − 175. Adding 7 to both sides yields 25^k+1 + 7 = 200j − 168 = 8(25j − 21). After eliminating the middle member of this equation, we have 25^k+1 + 7 = 8(25j − 21), showing that 8 is indeed a divisor of 25^k+1 + 7, and the clever proof is over.

Imagine how difficult it would be to compute 25⁸³⁷ + 7 in order to show that it is a multiple of 8.

GREATEST COMMON DIVISOR

Given a and b, we call d the greatest common divisor of a and b, denoted gcd(a,b), if:

1. d | a and d | b.
2. d is the greatest number that divides both a and b.

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,

• d = gcd(a,b) if and only if d = gcd(a, b − na), for any integer n

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 r_k = d = gcd(a,b). Note that r₁ > r₂ > r₃ > … > r_k = 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 = r_k)

(4.2)

From the equation before that one, we get r_k−1 = r_k−3 − q_k−1r_k−2, which allows us to rewrite (4.2) as d = r_k−2 − q_k(r_k−3 − q_k−1r_k−2) = −q_kr_k−3 + r_k−2 + q_kq_k−1r_k−2 or

(4.3)

Using the equation, r_k−4 = q_k−2r_k−3 + r_k−2, we can replace r_k−2 in (4.3) by r_k−4 − q_k−2r_k−3, obtaining

(4.4)

where A and B are expressions involving q_k−2, q_k−1, and q_k.

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.

1. Neither nor is an integer
2. and are reduced to lowest terms
3. b ≠ d

then their sum, , is not an integer.

DIOPHANTINE EQUATIONS

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 x₀ and y₀ (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(x₀ + bt) + b(y₀ − at) = ax₀ + abt + by₀ − bat = ax₀ + by₀ = c, since x₀ and y₀ 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 = x₀ + bt and y = y₀ − 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 (x₀, y₀) is also a solution. Subtracting ax₀ + by₀ = c yields a(x' − x₀) + b(y' − y₀) = 0, from which we have a(x' − x₀) = −b(y' − y₀). Since b divides the right side of this equation, it follows that b divides the left side, that is, b | a(x' − x₀). Furthermore, since gcd(a,b) = 1, we have b | (x' − x₀). Then x' − x₀ = bt, for some integer t. Inserting this into a(x' − x₀) = −b(y' − y₀) yields abt = −b(y' − y₀), which becomes at = −(y' − y₀). A drop of algebra then gives us x' = x₀ + bt and y' = y₀ − 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.

LEAST COMMON MULTIPLE

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:

1. Given two distinct positive integers G and L such that G | L, must there exist a pair of positive integers, a and b, with a < b, such that gcd(a,b) = G and lcm(a,b) = L?
2. If so, is the answer unique or are there several such pairs?
3. How many pairs are there?

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.

PRIME DECOMPOSITION

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 2² × 5². 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.

SEMIPRIME NUMBERS

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.

WHEN IS A NUMBER AN mTH POWER?

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 c^m?

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 = 2²5¹, and 600 = 2³3¹5². 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 2², which 30 does not contain.

TWIN PRIMES

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.

FERMAT PRIMES

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 | 2³² + 1. While this is easy to do today with the help of a computer, here is a number theoretic argument.

Let x = 2⁷ = 128 and let y = 5. Then 1 + xy = 1 + 5 × 128 = 641. We also have 1 + xy – y⁴ = 1 + y(x − y³) = 1 + 5 × 3 = 16 = 2⁴. Finally, 2³² + 1 = 2⁴2²⁸ + 1 = 2⁴(2⁷)⁴ + 1 = (1 + xy – y⁴)x⁴ + 1 = (1 + xy)x⁴ + (1 − x⁴y⁴) = (1 + xy)x⁴ + (1 − x²y²)(1 + x²y²) = (1 + xy)[x⁴ + (1 − xy)(1 + x²y²)] = 641[x⁴ + (1 − xy)(1 + x²y²)], 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 F_n. As of this writing, no Fermat primes have been found beyond F₄. Before we leave the topic of Fermat numbers, here is a theorem with a surprising consequence.

It follows that the nth Fermat number, F_n, contains at least one prime divisor that does not divide any of the Fermat numbers, F_m, where m < n. So there are infinitely many primes!

ODD PRIMES ARE DIFFERENCES OF SQUARES

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.

WHEN IS n A LINEAR COMBINATION OF a AND b?

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.

PRIME DECOMPOSITION OF n!

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 p₁, p₂, …, p_r, and let their exponents be e₁, e₂, …, e_r. So .

To determine e_i, first find the number of integers up to n containing p_i as a factor. This number is . For example, the number of integers up to 65 that contain 3 as a factor is , implying that 3²¹ | 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, 3⁴ 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.

NO NONCONSTANT POLYNOMIAL WITH INTEGER COEFFICIENTS ASSUMES ONLY PRIME VALUES

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 | aⁿ − bⁿ, 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 aⁿ − bⁿ and since we know that a − b | aⁿ − bⁿ, 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.

EXERCISES

An asterisk (*) indicates that the exercise can be developed into a research project.

1. Write a program to find the greatest common divisor of a given pair of positive integers. If the answer is 1, the program should state that the two numbers are relatively prime. Then find gcd(80,540), gcd(18,600), and gcd(105,350). At the end of the chapter, you can find a program that determines the GCD of the two numbers entered into the form by the user. See if you can add the message stating that two numbers are relatively prime when that is the case.
2. Verify that 6 | n³ − n for n ≤ 1000. Then prove it is true for all n.
3. Repeat the previous exercise for the statement 30 | n⁵ − n.
4. ^*If m and n are odd, show that 2 | m² + n² but 4 does not divide m² + n² for all m and n up to 1000.
5. ^*Show that a number of the form n(n + 1)(n + 2) is not a square for n ≤ 1000.
6. ^*Show that a number of the form n(n + 1)(n + 2) is not a cube for n ≤ 1000.
7. Given the distinct (unequal) positive integers a and b less than 100, show that is not an integer.
8. ^*Show that 4 | 3ⁿ + 1 when n is odd and less than 100. Try to prove this for all n.
9. Prove that 5 | u_5k, that is, show that every fifth Fibonacci number is a multiple of 5.
10. ^*For which positive even values of n up to 100 does 2n + 1 divide n⁴ + n²?
11. Find solutions of the Diophantine equations 6x + 9y = 21, 5x + 7y = 64, and 3x + 8y = 9.
12. Show that is prime for n = 0, 1, 2, 3, and 4.
13. Use one of the rounding functions to find f(n) if the values of f when n = 1, 2, 3, 4, 5, 6, 7, 8, and 9 are 1, 1, 1, 2, 2, 2, 3, 3, and 3, respectively.
14. How large can get? Assume that x is a positive real number.
15. Write n³ as the difference of two squares for all n ≤ 100.
16. Show that 2^r + 1 | 2^3r + 1 for all r ≤ 100.
17. Show that 4 does not divide n² + 1 for all n ≤ 100. Then show that this is true for all n.
18. Find the prime decomposition of 30!.
19. Let p be a prime number less than 101. Show that where 1 ≤ k ≤ p − 1.
20. Write a program that determines whether a given positive integer n is prime by checking whether it is divisible by any of the primes less than or equal to .
21. Write a program to find all the ways in which a given positive integer may be written as a product of two divisors. The program should also state the number of ways in which this can be done.
22. Verify Bertrand’s postulate (that for n > 1, there is a prime number between n and 2n) for all n such that 1 < n ≤ 1000.
23. ^*An arithmetic progression of length k is a sequence of the form a, a + d, a + 2d, a + 3d, …, a + (k − 1)d. The sequence 3, 7, 11, 15, 19, for example, is an arithmetic progression of length 5. Write a program that produces arithmetic progressions of length k consisting of primes. The sequence 5, 11, 17, 23, 29, for example, is an arithmetic progression of length 5 consisting of primes. Note that d = 6 is even. Explain why d must be even in an arithmetic progression of primes.
24. ^*Find 50 primes in the arithmetic progression 113, 213, 313, 413, … (in fact, there are infinitely many primes in this progression).

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>