A prime number is a number that has no divisors other than itself or 1. The subject of prime numbers is a big part of number theory.

PRIME NUMBERS AND PROOF BY CONTRADICTION

The first few primes are 2, 3, 5, 7, 11, 13, 17, and 19. A number that has divisors (or factors) other than itself and 1 is called composite. A composite number must have a prime divisor. Let n be a composite number. Then it has a factor, say, m, smaller than n. For example, 100 has the divisor 25. Now, if m is a prime, we have the desired prime divisor. If, on the other hand, m is composite, then m has a smaller divisor, say, k. Once again, if k is a prime, we have the desired prime divisor. If not, continue the process by producing a still smaller divisor, say, j, of k. Note that these divisors (m, j, and k) are divisors of the original number, n. Now, this process can’t go on forever, since n has finitely many divisors. It follows that sooner or later, this process produces a prime divisor.

The great Greek geometer and number theorist Euclid, who lived in Alexandria, Egypt, circa 300 b.c., proved that there are infinitely many primes. He began by assuming that there are only finitely many primes and proceeded to obtain a contradiction. (The proof may have been known before Euclid wrote it down in his 13-volume book, “Elements.”)

If there are finitely many primes, call them a, b, c, and so on up to the supposed last (or greatest) prime, say, p. Then any number larger than p is a composite number, since we are assuming that p is the largest prime. Now, let N = abc…p (i.e., N is the product of all the primes), and then consider the larger number N + 1 (same as abc…p + 1). Since this number is greater than p, it is a composite number. Then it must have a prime divisor. But this prime divisor is clearly a divisor of N (since N is the product of all the primes) and cannot, therefore, be a factor of N + 1. This is a contradiction! It follows that the initial assumption that there is a largest prime is mistaken. Then there are infinitely many prime numbers.

As a consequence of the above example, to determine whether a given number is a prime, it suffices to check whether it is divisible by any of the numbers less than or equal to its square root.

Example of 41 continued: Since 2 does not go into 41, neither does 4 or 6. Finally, since neither 3 nor 5 goes into 41, we are done. 41 is a prime number.

All numbers have exactly one of the forms 4k, 4k + 1, 4k + 2, and 4k + 3. Thus, 7, for example, is of the form 4k + 3, as can be seen by letting k = 1. On the other hand, 21 is of the form 4k + 1, as can be seen by letting k = 5. It is obvious that numbers of the form 4k or 4k + 2 are composite (except for 2, the only even prime). This leaves the two “classes” of numbers of the forms 4k + 1 and 4k + 3. Each class contains infinitely many primes.

PROOF BY CONSTRUCTION

Many proofs employ construction, that is, the claim of the theorem is proven by constructing a general example. Here are two theorems illustrating this idea. To understand the first proof, recall that n!, read “n factorial,” is the product of the first n positive integers, that is,

SUMS OF TWO SQUARES

BUILDING A PROOF ON PRIOR ASSERTIONS

Many assertions in mathematics are proven by invoking prior proven assertions. Here is an example. Let us prove that n^k, where n and k are given positive integers greater than 1, is the sum of n consecutive odd numbers beginning with n^k−1 − n + 1. That is, show that

Note that the constants in parentheses are the first n odd numbers, 1, 3, 5, …, 2n − 1, which we know have the sum n². Note also that the expression n^k−1 − n occurs in each of the n parentheses. Then the sum on the right in the above equation is n(n^k−1 − n) + n² = n^k − n² + n² = n^k, and the proof is complete.

When k = 3, we get , proving the following theorem.

SIGMA NOTATION

Sigma notation is a convenient device for writing large sums. It involves a variable that is present in each term and that changes values consecutively. Thus, the sum can be written by employing the variable m and noting that m goes from 1 to 100, consecutively. The command to add the terms is simply . The numbers under and over the capital sigma indicate where to start and where to stop. The function of m in front of the sigma indicates the typical expression being added.

Now, some sums are tricky in that the number of terms is variable, such as “the sum of the first n odd numbers.” Since the mth odd number is 2m − 1, we write . We call m a dummy variable since, unlike n, it doesn’t survive the addition, and it varies as we evaluate the expression. (Note that n stays constant.) Note that many sums employing sigma can be computed with a simple “for-loop.”

SOME SUMS

Here are some formulas for the sum of the first n powers:

(2.1)

(2.2)

Recall that an oblong number has the form k(k + 1). The first few oblong numbers are 2, 6, 12, 20, and 30. The sum of the first n oblong numbers is given by

(2.3)

If we divide both sides of (2.3) by 2, we get, as a bonus, the following formula for the sum of the first n triangular numbers:

(2.4)

FINDING ARITHMETIC FUNCTIONS

Let n be an integer. Then f(n) is arithmetic if f(n) is an integer. Thus, f(n) = 2n³ is arithmetic. We present a way of finding arithmetic functions from several values of f(n). Look at the chart plotting n against f(n), for n = 1, 2, 3, and 4. Let us find a function that does this.

Infinitely many functions can do the job. But if we assume that the pattern of values persists ( f(n) seems to grow by the same amount, viz., 3, from row to row, i.e., the so-called first differences, f(n + 1) − f(n), are constant), the function might be linear, or first degree. Then we set f(n) = an + b and proceed to find a and b. Two unknowns generally require two equations, so we use the facts that f(1) = 5 and f(2) = 8. This yields the simultaneous equations:

with solution a = 3 and b = 2. Our function is f(n) = 3n + 2. This works if the first differences of the function f are constant. The first differences are constant if and only if f(n) is of the form an + b. A calculation of the first differences yields f(n + 1) − f(n) = a(n + 1) + b − (an + b) = an + a + b − an − b = a, which is a constant, independent of n. If you plot the points in the chart, they will lie on a straight line, that is, the line y = ax + b. Now, a straight line has constant slope, namely, . Since the x values are 1, 2, 3, …, we have Δx = 1. Since the y values jump by the constant value a, we have Δy = a. Then the slope is a, which is in perfect agreement with the equation y = ax + b.

Assuming, from the handful of known values for the first few integers, that a function is a polynomial, how do we infer its degree from its chart of values and how do we determine the coefficients? To answer these questions, let’s define kth order differences. The next chart shows f(n) and its successive differences Δ₁f, Δ₂f, and Δ₃f. Now, Δ₁f is the first difference we used in the previous problem.

The fourth column, labeled Δ₂f, yields the differences of Δ₁f, which are called the second differences of f(n). Similarly, the quantities Δ₃f are called the third differences. This process could go on forever, but if the arithmetic function f(n) is a polynomial of degree k, it can be shown that Δ_kf is constant so all differences of order greater than k are zero.

Once it is determined from a chart (again, assuming persistence of the pattern) that f(n) has degree k, one can find the k + 1 coefficients of the polynomial using the first k + 1 values of f. Since the third differences are constant here, we require a cubic function, f(n) = an³ + bn² + cn + d. The determination of the four coefficients requires four equations, in turn requiring the first four values f(1) = 3, f(2) = 11, f(3) = 31, and f(4) = 69. We get four equations in four unknowns by letting n = 1, 2, 3, and 4 in the equation for f(n):

whose solution a = 1, b = 0, c = 1, and d = 1 can be obtained by first subtracting each of first three equations from its successor, yielding three equations in three unknowns:

Repeating the same technique yields

whose solution is a = 1, b = 0. Plugging these values into the original four equations in four unknowns yields two equations in two unknowns. We finally obtain the desired function, f(n) = n³ + n + 1. Note that this is true for every value listed in the chart.

Since the second differences are constant, we look for a quadratic function, f(n) = an² + bn + c. Using the first three values f(1) = 1, f(2) = 3, and f(3) = 6, we get the three equations

yielding , , and c = 0. Then .

FIBONACCI NUMBERS

In the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …, each term is the sum of the preceding two terms. We denote these Fibonacci numbers by u₁, u₂, u₃, …. Thus, u_n is the nth Fibonacci number. Now, u₁ = 1 and u₂ = 1 are the seed since they determine the rest of the terms. (For example, u₃ = u₁ + u₂ = 1 + 1 = 2.) The relationship between the general term and the two preceding terms is called the recursive relation and is written as

(2.5)

When n = 3, this becomes u₅ = u₃ + u₄ = 2 + 3 = 5. While the Fibonacci numbers get arbitrarily large, an odd thing happens when we study the sequence of ratios of the form , that is, the ratios consisting of each term divided by its predecessor. The first few such ratios are , which makes us suspect that the ratios approach a limit. The limit is the famous irrational number, denoted by the Greek letter φ, known as the golden ratio. (Its approximate value is 1.618.) To show this, divide both sides of (2.5) by u_n+1, yielding the equation

(2.6)

Let L denote the limit of the ratios we seek. As n approaches infinity, the left side of (2.6) approaches L. (u_n+1 is the predecessor of u_n+2.) On the other hand, the first term on the right side of (2.6) is the reciprocal of the ratio we are considering, since the numerator u_n is the predecessor of the denominator u_n+1. Then this term approaches .

Inserting these values into (2.6) yields . Multiplying both sides by L and transposing everything to the left yields L² − L − 1 = 0, whose positive root yields L, or φ as it is commonly called. The positive root is .

Suppose you live in a country whose currency consists solely of one and two dollar bills. Given n, we wish to count the number of ways of putting n dollars into a vending machine using one and two dollar bills. Let us agree to consider order as a differentiating factor, as well as the quantities of both kinds of bills. In technical terms, we are counting ordered partitions of n using 1’s and 2’s. Denote the function that counts these partitions by f(n). When n = 3, for example, we have the following three possibilities:

so f(3) = 3. When n = 4, we have the following five possibilities:

indicating that f(4) = 5. Finally, when n = 5, we have the following eight possibilities:

in which case, f(5) = 8. The cases n = 1 and n = 2 are easy. When n = 1, we have the single possibility, 1, while when n = 2, we have two possibilities, 2 and 1 + 1, so f(1) = 1 and f(2) = 2.

In summary, the first five values of f(n) are 1, 2, 3, 5, and 8. It seems like we obtained the Fibonacci numbers u₂, u₃, u₄, u₅, and u₆. One would be tempted to guess that f(n) = u_n+1. To prove this amazing fact, observe that it works in the first few instances. It suffices, therefore, to show that the function f(n) obeys the recursive relation of the Fibonacci numbers, that is, we must show that f(n + 2) = f(n) + f(n + 1).

Ordered partitions of n + 2 consisting of 1’s and 2’s can be divided into two piles. The first pile will include all partitions that begin with 2, while the second pile will consist of the remaining partitions, that is, those that begin with 1. The number of partitions in the first pile is clearly f(n) since 2 is the first term of each of these partitions, requiring that we complete the process by partitioning n. By the same token, the number of partitions in the second pile is clearly f(n + 1) since 1 is the first term of each of these partitions, requiring that we complete the process by partitioning n + 1. Thus, f(n + 2) = f(n) + f(n + 1). Partitions play a significant role in number theory.

Here is a theorem that yields the sum of the first n terms of the Fibonacci sequence.

(2.7)

(2.8)

There is a formula in terms of n for finding u_n. It is called Binet’s formula.

(2.9)

Who would believe that a formula for the Fibonacci numbers could involve ?

AN INFINITE PRODUCT

Consider the product of the expressions as k goes from 2 to some given number, n. When n = 5, for example, we get

Let us find the general product as a function of the given number, n. Observing that

we get

since everything else cancels. This last expression equals , or . (When n = 5, we get 3/5, which is in perfect agreement with the answer we obtained earlier.) Now, what happens if we let n got to infinity? In other words, what if we take the product of the expressions 1 − 1/k² where k ranges over all the numbers from 2 to infinity? Since the product up to n is , and since the second fraction, , goes to zero as n goes to infinity, the answer is .

THE PELL EQUATION

When are x² and 2y² consecutive? x = y = 1 yields a solution since 1 and 2 are consecutive. The solution x = 3 and y = 2 produces the consecutive numbers 8 and 9. Indeed, 8 is twice a square and 9 is a square.

Does this happen again? x = 7 and y = 5 yield the consecutive pair 49 and 50. The solution yielding the consecutive numbers 8 and 9 differs from the solution yielding the consecutive numbers 49 and 50, since in the first, the square exceeds the “doubled square,” while in the second, the doubled square exceeds the square. So we rephrase the question, “when is x² − 2y² = ±1?” This happens infinitely often.

Assume that we have a solution, x and y, such that x² − 2y² = ±1. Consider the following recursive relation between these known numbers x and y and the new numbers x′ and y′ given by the equations

Now, observe that x′² − 2y′² = (x + 2y)² − 2(x + y)² = x² + 4xy + 4y² − 2x² − 4xy − 2y² = −x² + 2y² = −(x² − 2y²). Since we know that x² − 2y² = ±1, it follows that x′² − 2y′² = −(±1). The point is that this recursive procedure generates infinitely many pairs (x, y) such that x² − 2y² = ±1, with each pair larger than the preceding one, since x′ > x and y′ > y.

The chart below gives the first few pairs generated by the recursive relation.

An equation of the form

(2.10)

where k ≥ 2, is called a Pell equation. We will see other uses for Pell equations later.

Here is a method for finding infinitely many solutions of (2.10) when the right side is 1.

So now x² − ky² = 1. The first step is to find a pair of positive integers a and b that satisfy this equation, that is, a and b satisfy a² − kb² = 1. Keep in mind that a and b are guesses for x and y. For example, x² − 2y² = 1 has a solution x = a = 3 and y = b = 2. Then 3² − 2 · 2² = 1. So if n is any positive integer, (a² − kb²)ⁿ = 1ⁿ = 1.

Now, suppose that x and y also satisfy x² − ky² = 1. Then for any n = 1, 2, 3, 4, …, we have

(2.11)

since a² − kb² = 1.

The next step is to factor both x² − ky² and a² − kb² as the difference of two squares even though k might not be a square. Then (2.11) becomes

Now, one solution of an equation of the form AB = CD can be A = C and B = D. Of course, there are many other possibilities. But let’s use this approach. This yields the following pair of equations:

To solve for x, add these equations and divide by 2. To solve for y, subtract and divide by . We obtain the infinitely many solutions

These equations yield positive integers despite the presence of . To show this, one applies the binomial theorem. We won’t do this here.

What is the point of all this? Recall that a triangular number has the form . In other words, it is half the product of two consecutive numbers. Consider (xy)² obtained from any pair (x, y) in the chart. It is clearly a square, but we claim that it is also a triangular number. If so, we have a proof of the following theorem.

The ancient Greeks, by the way, used this chart to approximate . Dividing both sides of x² − 2y² = ±1 by y² yields

As we descend the chart, it is clear that y approaches infinity, implying that the square of its reciprocal goes to 0, that is, . Then the left side of the above equation also approaches 0, in which case approaches 2, implying that the ratio approaches .

Notice that the first five ratios from the chart are 1, 1.5, 1.4, 1.417, and 1.414, rounded to three places. They alternately underestimate and overestimate the actual value. This trend continues forever.

GOLDBACH’S CONJECTURE

Number theory is an old but still vibrant field of mathematics. In the eighteenth century, Goldbach conjectured that every even number greater than 4 is the sum of two odd primes. This has still not been proven! An exercise suggests that you confirm this conjecture by testing the numbers 4 to 1000. (This is not a proof! Something could go wrong for numbers greater than 1000.)

EXERCISES

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

1. Find all primes less than 1000. See if you can do this on your own. Refer to the examples if and when you like. Note: programs can be improved, especially in presentation.
2. Show that the first 100 primes greater than 3 are either of the form 6k + 1 or 6k + 5.
3. Find 100 primes of the form 6k + 5.
4. Prove the claim that , by showing that it is true for all n ≤ 100. Now, try to prove it.
5. Prove the claim that .
6. Use the chart method to find the sum of the first n fourth powers. Test it for all n ≤ 100.
7. Write a program to add up f(n) for n = 1, 2, …, N where f(n) = an³ + bn² + cn + d. The user inputs the integers a, b, c, d, and N. Your program should not employ any of the summation formulas of the chapter. In other words, the program should calculate f(n) for each n = 1, 2, …, N and add the results to a running sum. Then find . Does it matter that the dummy variable is k instead of n?
8. Repeat the previous exercise using the summation laws given by formulas (2.1) and (2.2). How will you handle cn + d? Which program is faster for large values of N?
9. ^*13 is the smallest prime such that reversing its digits yields a different prime, namely, 31. Find five more primes with this property.
10. Show that none of the first 100 triangular numbers are the sum of two consecutive squares.
11. Write a program to find the first 50 Fibonacci numbers.
12. Show that the only cubes among the Fibonacci numbers in the previous exercise are 1 and 8.
13. ^*The Fibonacci numbers 1 and 3 are triangular. Find two more triangular Fibonacci numbers.
14. Verify that for k ≤ 100, u_3k is even while the rest are odd. Then prove this for all values of k.
15. Verify that for k ≤ 100, we have .
16. Verify that for k ≤ 100, we have .
17. Verify that for n ≤ 100, we have u_n ≤ 2ⁿ⁻¹.
18. ^*Verify that for n ≤ 100, we have u_n² − u_n+1u_n−1 = (−1)ⁿ⁻¹.
19. Find , by distributing the sigma and then factoring out the coefficients of each term containing k. Then use a program.
20. Verify that for n ≤ 100, the sum of the first n triangular numbers is .
21. ^*In the eighteenth century, Goldbach conjectured that every even number greater than 4 is the sum of two odd primes. This has still not been proven! Verify the conjecture for the even numbers from 4 to 100. You can examine the sample program that does the work for a specific number.
22. Write a program that finds all the ways to write a given even integer n ≥ 6 as the sum of two odd primes.
23. Verify that every odd number between 9 and 51 is the sum of three odd primes.
24. ^*The Ulam sequence starts with the numbers 1, 2, and 3. Each successive number is the next number that is uniquely expressible as the sum of two previous sequence terms. The next number after 1, 2, 3 is 4 since 4 = 1 + 3 and there is no other way to write 4 as the sum of two of the numbers 1, 2, and 3. The next term after 1, 2, 3, 4 is not 5, since 5 = 1 + 4 and 5 = 2 + 3. It is 6, since 6 is uniquely 2 + 4. Find the first 100 terms of the Ulam sequence.
25. ^*The Crunchy sequence starts with the numbers 1, 2, 3, and 4. Each successive number after 4 is the next number that is uniquely expressible as the product of two previous sequence terms. The next number after 1, 2, 3, 4 is 6 since 6 = 2 × 3 and there is no other way to write 6 as the product of two of the numbers 1, 2, 3, and 4. The next term after 1, 2, 3, 4, 6 is 8, since 8 = 2 × 4. Note that 12 is excluded since 12 = 3 × 4 and 12 = 2 × 6. The next two terms are 16 and 18. Find the next 50 terms of the Crunchy sequence. Note whether they are prime or composite.
26. ^*Show that the terms of the Crunchy sequence obtained in the previous exercise have the form 2ⁿ3^m.
27. ^*Prove that the values of x and y in the chart found in this chapter containing solutions to the Pell equation x² − 2y² = ±1 (if we extend the chart to produce 30 solutions) have the following properties.

    x is always odd.

    The parity of y alternates. (y strictly alternates between odd and even values.)

    When both of x and y are odd, the integers , , and y satisfy the Pythagorean theorem, that is, .

    x and y have no common factor other than 1. Another way to say this is that x and y are relatively prime.

    When y is even, let y = 2k. Then show that 8k² + 1 is a square.

28. Write a program to find all solutions to the Pell equation x² − 3y² = 1, where x and y are positive integers and x ≤ 1000. See comment on Exercise 1.
29. For each n ≤ 10,000, determine the number of ways in which n can be written as the sum of two squares. (In some cases, the answer will be zero.) Now, take the average of all your answers.

Basic Program Listing Primes

<!DOCTYPE html>
<head>
<meta charset="UTF-8">
<title>Prime number example </title>
<script>
 
function init(){
for (n=3;n<1000;n++){
  //check if n is a prime
  //first obtain its square root.
  //We make use of a built-in function in JavaScript
  s=Math.sqrt(n);
  //we have proved n is NOT a prime if we find a factor. 
  //we set up what is termed a flag variable. It starts
//out being true.
  noFactorSoFar = true;
  for (f=2;f<=s;f++){
      //is f a factor of n?  We make use of the modulo
//operator, %. 
     //It essentially produces the remainder
     r = n % f;
     // r being zero means no remainder, n was
//divisible by f
     if (r==0){
       noFactorSoFar = false;
       break;    // leave the inner f loop because we
//found a factor
     }
     // continue with f loop
  } // ends the f loop
  if (noFactorSoFar){
    //never found a factor
    document.write(n)
    document.write("<br/>");
  }


} // ends the n loop
}
init();
</script>
</head>
<body>
Primes up to 1000
</body>
</html>

Basic Program, with Counting of Mod Operation

<!DOCTYPE html>
<html>
<head>
<title>Listing primes</title>
<script>
 

function init(){
  count = 0;
  np = 0;
  for (n=3;n<1000;n++){
  //check if n is a prime
  //first obtain its square root. 
  //We make use of a built-in function in JavaScript
  
   s=Math.sqrt(n);
  //we have proved n is NOT a prime if we find a factor. 
  //we set up what is termed a flag variable. It starts
//out being true.
   noFactorSoFar = true;
   for (f=2;f<=s;f++){
      //is f a factor of n?  We make use of the modulo
//operator, %. 
     //It essentially produces the remainder
     r = n % f;
     count++;
     // r being zero means no remainder, n was
//divisible by f
     if (r==0){
       noFactorSoFar = false;
       break;   // leave the inner f loop because we
//found a factor
     }
     // continue with f loop
   } // ends the f loop
   if (noFactorSoFar){
    //never found a factor
    document.write(n)
    document.write("<br/>");
    np++;
   }
  } // ends the n loop
  document.write("Number of % operations
performed: " + count+"<br/>");
  document.write("Number of primes (starting with
3):"+ np);
}
init();
</script>

</head>
<body>
<hr/>
Check done using all numbers less than the square root.
</body>
</html>

Improved Program, Just Checking Primes

<!DOCTYPE HTML>
<html>
<head>
<title>Faster Listing of Primes </title>
<script>
var primes=[2];   //we treat 2 as a prime
function init(){
     count = 0;
     np=0;
   for (n=3;n<1000;n++){
     //check if n is a prime
     //first obtain its square root. 
     //We make use of a built-in function in
//JavaScript
 
       s=Math.sqrt(n);
     //we have proved n is NOT a prime if we find a
//factor. 
     //we set up what is termed a flag variable. 
     //It starts out being true.
       noFactorSoFar = true;
     //instead of checking all the numbers, we just
//check the primes
     // the && does a logical AND test BUT 
     // it will only calculate the second term
     // if the first is true. This is sometimes
//called "lazy".

       for (fi=0;fi<primes.length && primes[fi]
<=s;fi++){
     //is f a factor of n?  We make use of the modulo
//operator, %. 
     //It essentially produces the remainder
       f=primes[fi];
       r = n % f;
     // r being zero means no remainder, n was
//divisible by f
       count++;
       if (r==0){
         noFactorSoFar = false;
         break;  
         // leave the inner f loop because we found
//a factor
        }
     // continue with f loop
      } // ends the f loop
      if (noFactorSoFar){
    //never found a factor
       document.write(n)
       document.write("<br/>");
       primes.push(n);
//add n to our list (array) of primes
        np++; }
   } // ends the n loop

   document.write("Number of % operations
performed: " + count+"<br/>");
   document.write("Number of primes (starting with 3):" + np);
}
init();
</script>
</head>
<body>
<hr/>
Check done by building up list of primes and only
checking for division by primes.

</body>
</html>

Basic Solution to a Pell Equation, Using Procedure

<!DOCTYPE HTML>
<html>
<head>
<title>Pell solutions k=3 </title>
<script>
 
function init(){
      //guessed a = 2, b = 1.
  //k is 3
  document.write("Solutions of x2 - 3*y2 = 1");
  document.write("<hr/>");
  a=2;
  b=1;
  k=3;
  //start with n set to 1. This will produce the x=a
//and y=b values (3,1)
  for(n=1;n<=1000;n++){
    if (produceXandY(a,b,k,n)) break;  
//stop when x is over limit

//break out of loop way before n is 1000
  }
  
}
function produceXandY(a,b,k,n) {
  var x;
  var y;
  var sqrtK = Math.sqrt(k);
  var sqrtKB = sqrtK*b;
  var f1 = a+sqrtKB;
  var f2 = a-sqrtKB;
  var t1n = Math.pow(f1,n);
  var t2n = Math.pow(f2,n);
  x = (t1n + t2n)/2;
  y = (t1n-t2n)/(2*sqrtK);
  //next 2 statements necessary because method
//generates numbers like 2.99999998
  //this is due to limited precision so, for
//examples, values based on sqrt(3) may not cancel
  x = Math.floor(x+.5);

  y = Math.floor(y+.5);
  if (x>1000) {return true;}
  else {
  document.write("x = "+ String(x)+ ", y = "+String
(y)+ "<br/>");
  return false;
   }
}
init();
</script>
</head>
<body>
<hr/>
Check done based on "guess" of x=a=3 and y=b=1 and
then using procedure to iterate
 
</body>
</html>

Solving a Pell Equation by Direct Calculation and Checking if Answer Is an Integer

<!DOCTYPE HTML>
<html>
<head>
<title>Pell solutions k=3 crude</title>
<script>
function init(){
  
  //k is 3
  document.write("Solutions of x2 - 3*y2 = 1");
  document.write("<hr/>");
  
  k=3;
 
  //start with n set to 1. This will produce the x=a and
  //y=b values (3,1)
  for(x=1;x<1000;x++){
   h = (x*x-1)/k;
   yy = Math.sqrt(h);
   y  = Math.floor(yy+.5);

  //idea is that the rounded off integer value
//won't work
  if ((x*x-3*y*y)==1) {
  document.write("x = "+ String(x)+ ", y = "+String
(y)+ "<br/>");
  }
 }
}
init();
</script>
</head>
<body>
<hr/>
Crude procedure checking for each value of x, the computed value of y, taking the positive square root
</body>
</html>

Interactive Program to Generate Pairs of Primes Addingup to Even Number

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>Numbers as sum of 2 primes </title>
<script>
var primes=[2];   //we treat 2 as a prime
var limit = 1000;
function init(){
  var f;
  var r;
  var noFactorSoFar;
  var s;
  for (var n=3;n<limit;n++){
  //check if n is a prime for each n
  //first obtain its square root. We make use of a
//built-in function in JavaScript

    s=Math.sqrt(n);
  //we have proved n is NOT a prime if we find a factor. 

  //we set up what is termed a flag variable. It starts
//out being true.
    noFactorSoFar = true;
  //instead of checking all the numbers, we just
//check the primes
  // the && does a logical AND test BUT it will only
//calculate the second term
  // if the first is true. This is sometimes
//called "lazy".
    for (var fi=0;fi<primes.length && primes[fi]
<=s;fi++){
     //is f a factor of n?  We make use of the modulo
//operator, %. 
      //It essentially produces the remainder
        f=primes[fi];
        r = n % f;
      // r being zero means no remainder, n was
//divisible by f
         if (r==0){
           noFactorSoFar = false;
           break;
// leave the inner f loop because we found a factor
        }
     // continue with fi loop
   } // ends the fi loop
      if (noFactorSoFar){
   //never found a factor
      primes.push(n);  of primes        
      
   }} // ends the n loop
}
function findpairs() {
//add n to our list (array) of primes
  answer = "";  
//will use to construct the answer
  count = 0;   var h;
  var number = parseInt(document.f.num.value);
//extract what the user entered
  if ((number%2)>0) {
    alert("Your number must be even. Try again");
    return false;}

  if (number > limit) {
    alert("Your number is greater than "+limit+".
Please try a smaller number.");
   return false;
  }
  h = number / 2;
  for (f=1;f<=h;f++){
    //need to check if f and (number-f) both primes.
//Use lazy evaluation 
   if (isPrime(f) && isPrime(number-f)) {
     answer += String(f)+ " and "+ String(number-f)
+" <br/>";
     count++;
   }
 }

 if (answer.length>0) { //were any pairs found?
     answer +=String(count)+" pairs of primes
adding up to "+String(number);
      
  }
  else { //this may never happen???
     answer = document.createTextNode("No pairs of
primes adding up to "+String(number));
  }
  document.getElementById("place").innerHTML =
answer;
  return false;
// required to prevent the browser from re-loading
original document
}
function isPrime(c) {
  var i;
  i = primes.indexOf(c);
  return (i>=0);
//i greater or equal to zero means that c is in the
primes array
 
}
</script>
</head>
<body onload="init();">
Find pair of prime numbers adding up to even number <br/>
<form name="f" onsubmit="return findpairs();">
  <input type="text" name="num" value="  "/>
  <input type="submit" value="Submit an even number "/>
</form>
<p id="place">
  The answer will go here.
</p>
</body>
</html>