Number theory

Twin primes are pairs of primes that differ by 2. For example, 3 and 5 are twin primes, as are 17 and 19. Importantly, so are 824633702441 and 824633702443. More on that in a minute.

No one knows whether there is a largest pair of twin primes. The twin prime conjecture says that there are infinitely many pairs of twin primes, but the conjecture has not been proven.

Now suppose we take the reciprocals of the twin primes and add them up.

If there were only finitely many twin primes, the sum would have finitely many terms and hence a finite sum. But the sum might converge even though it has infinitely many terms. On the other hand, if we could show that the sum diverges, we’d have a proof of the twin prime conjecture. Viggo Brun showed that the sum does converge. Its sum, known as Brun’s constant, is a little more than 1.9.

In 1994, Thomas Nicely was studying Brun’s constant when he found that his computer incorrectly computed 1/824633702441 beyond the eighth significant figure. Nicely had discovered the infamous Pentium division bug.

Intel responded by saying the division errors were inconsequential. Intel was absolutely correct, but the public couldn’t understand that. They only knew that the chips were “wrong.”

The error was estimated to occur once in every 9 billion divisions. (I doubt any large program has ever been written that is as bug-free as the buggy Pentium chips.) And when an error did occur, the result was not entirely wrong, only less accurate than usual. The public only understood that sometimes the answers were “wrong.” Most people do not understand that floating point arithmetic is nearly always “wrong” in the sense of being less than perfectly accurate.

At first Intel said it would only replace the chips for people who could show they were effected by the bug, i.e. almost nobody. Eventually Intel gave in to pressure and replaced the chips. The episode cost Intel half a billion dollars.

Related posts:

Odd perfect numbers
Probability that a number is prime

Yesterday I wrote about even perfect numbers. What about odd perfect numbers? Well, there may not be any.

I couldn’t care less about perfect numbers, even or odd. But I find the history and the mathematics surrounding the study of perfect numbers interesting.

As soon as you define perfect numbers and start looking for examples, you soon realize that all your examples are even. So people have wondered about the existence of odd perfect numbers for at least 2300 years.

No one has proved that odd perfect numbers do or do not exist. But people have proved properties that odd perfect number must have, if there are any.  So far, although the requirements for odd perfect numbers have become more demanding, they are not contradictory and it remains logically possible that such numbers exist. However, most experts believe odd perfect numbers probably don’t exist. (Either odd perfect numbers exist or they don’t. How can one say they “probably” don’t exist? See an explanation here.)

Wikipedia lists properties that odd perfect numbers must have. For example, an odd perfect number must have at least 300 digits. It’s interesting to think how someone determined that. In principle, you could just start at 1 and test odd numbers to see whether they’re perfect. But in practice, you just won’t get very far.

A year is about 10^7.5 seconds (see here). If you had started testing a billion (10^9) numbers a second since the time of Euclid (roughly 10^3.5 years ago) you could have tested about 10^20 numbers by now. Clearly whoever came up with the requirement N > 10^300 didn’t simply use brute force. There may have been some computer calculation involved, but if so it had a sophisticated starting point.

I just got a review copy of Maths 1001 by Richard Elwes. As the title may suggest, the book is a collection 1001 little math articles. (Or “maths articles” as the author would say since he’s English.) Most of the articles are elementary though some are an introduction to advanced topics. Here’s something I learned from an article that was somewhere in the middle, the connection between perfect numbers and Mersenne primes.

Euclid (fl. 300 BC) proved that if M is a Mersenne prime then M(M+1)/2 is perfect. (A number is “perfect” if it equals the sum of its divisors less than itself. For example, 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14. A Mersenne prime is a prime of the form 2ⁿ – 1.) Euclid didn’t use the term “Mersenne prime” because Mersenne would come along nearly two millennia later, but that’s how we’d state Euclid’s result in modern terminology.

The converse of Euclid’s result is also true. If N is an even perfect number, then N = M(M+1)/2 where M is a Mersenne prime. Ibn Al-Haytham conjectured this result in the 10th century but it was first proved by Leonard Euler in the 18th century. (What about odd perfect numbers? See the next post.)

I’ve enjoyed reading Maths 1001. I’ll flip through a few pages thinking the material is all familiar but then something like the story above will stand out.

Update: Richard Elwes informs me that his book is published under the title Mathematics 1001 in the US. My review copy was a British edition.

We all learn in elementary school that a number is divisible by 2 if the last digit is even. A number is divisible by 3 if the sum of the digits is divisible by 3. A number is divisible by 5 if its last digit is 0 or 5. Etc.

But imagine we were born with 8 fingers on each hand and did arithmetic in base 16, also called hexadecimal. Or suppose schools decided to teach children hexadecimal instead of decimal to give them a head start in computer science. We would count 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, 10, 11, …

What would divisibility rules look like? Here are the simplest rules.

• n divisible by 2 if its last digit is even.
• n is divisible by 3 if its digit sum is divisible by 3.
• n is divisible by 4 if its last digit is 0, 4, 8, or C.
• n is divisible by 5 if its digit sum is divisible by 5.
• n is divisible by 6 if it is divisible by 2 and 3.
• n is divisible by 8 if it ends in 0 or 8.
• n is divisible by A if it is divisible by 2 and 5.
• n is divisible by F if its digit sum is divisible by F.
• n is divisible by 10 (i.e. sixteen) if its last digit is 0.

In this list “digit” means hexadecimal digit.

There are also rules for checking divisibility by 7 and 11 (i.e. seventeen) in hexadecimal analogous to the rules for divisibility by 7 and 11 in decimal.

To test divisibility by 7, split off the last digit from the rest of the number. Triple it and subtract from what’s left of the original number. Repeat this process until you get something you recognize as being divisible by 7 or not.

For example, suppose you start with F61. Split this into F6 and 1. Subtract 3 from F6 to get F3. Now split F3 into F and 3. Subtract 9 from F to get 6. F61 is not divisible by 7 because 6 is not divisible by 7. The explanation for how this works is completely analogous to the corresponding rule in base 10.

You can test for divisibility by 11 in base 16 (i.e. by seventeen) just as you’d test divisibility by 11 in base 10 (or any other base). Add up the digits in an odd position and subtract the sum of the digits in an even position. For example, suppose you start with 135B8. The digits in odd position sum to 1 + 5 + 8. The digits in even positions sum to 3 + B. Both sums are equal, so there difference is 0, which is divisible by 11, so 135B8 is divisible by 11.

There’s nothing special about base 16 or base 10. You could come up with analogous divisibility rules in any base.

Related posts:

Divisibility by 7
Probability that a number is prime

How can you tell whether a number is divisible by 7? Most everyone knows how to easily tell whether a number is divisible by 2, 3, 5, or 9. A few less know tricks for testing divisibility by 4, 6, 8, or 11. But not many people have ever seen a trick for testing divisibility by 7.

Here’s the trick. Remove the last digit from the number, double it, and subtract it from the first part of the number. Do this repeatedly until you get something you recognize as being divisible by 7 or not.

For example, start with 432. Split into 43 and 2. Subtract 4 from 43 to get 39. Since 39 isn’t divisible by 7, neither is 432.

For another example, start with 8631. Split into 863 and 1. Subtract 2 from 863 to get 861.

Now split 861 into Split into 86 and 1. Subtract 2 from 86. Maybe you recognize 84 as a multiple of 7. If not, double 4 and subtract from 8 to get 0, which is divisible by 7. Either way, we conclude that 8631 is divisible by 7.

Why does this work? Let b be the last digit of a number n and let a be the number we get when we split off b. That says n = 10a + b. Now n is divisible by 7 if and only if n – 21b is divisible by 7. But n – 21b = 10(a – 2b) and this is divisible by 7 if and only if a – 2b is divisible by 7.

What about the remainder when you divide a number by 7? Here’s where the rule for 7 differs from the more familiar divisibility rules. For example, a number is divisible by 3 if its digit sum is divisible by 3, and furthermore the remainder when a number is divided by 3 is the remainder when its digit sum is divided by 3. But the divisibility rule for 7 does not give the remainder when a number is divided by 7. For a simple example, the divisibility rule for 31 terminates in 1, but the remainder with 31 is divided by 7 is 3.

Why doesn’t the divisibility rule for 7 give the remainder? It is true that 10a + b and (10a + b) – 21b have the same remainder when divided by 7. But then we factored this into 10(a -2b). It’s true that 10(a – 2b) is divisible by 7 if and only if (a – 2b) is divisible by 7, but if neither is divisible by 7 then they will leave different remainders.

Related posts:

Divisibility rules in other bases
Fast way to tell whether a number is a square
Roots of integers
Probability that a number is prime

Suppose you have a number x between 0 and 1. You want to find a rational approximation for x, but you only want to consider fractions with denominators below a given limit.

For example, suppose x = 1/e = 0.367879…  Rational approximations with powers of 10 in the denominator are trivial to find: 3/10, 36/100, 367/1000, etc. But say you’re willing to have a denominator as large as 10. Could you do better than 3/10? Yes, 3/8 = 0.375 is a better approximation. What about denominators no larger than 100? Then 32/87 = 0.36781… is the best choice, much better than 36/100.

How do you find the best approximations? You could do a brute force search. For example, if the maximum denominator size is N, you could try all fractions with denominators less than or equal to N. But there’s a much more efficient algorithm. The algorithm is related to the Farey sequence named after John Farey, though I don’t know whether he invented the algorithm.

The idea is to start with two fractions, a/b = 0/1 and c/d = 1/1. We update either a/b or c/d at each step so that a/b will be the best lower bound of x with denominator no bigger than b, and c/d will be the best upper bound with denominator no bigger than d. At each step we do a sort of binary search by introducing the mediant of the upper and lower bounds. The mediant of a/b and c/d is the fraction (a+c)/(b+d) which always lies between a/b and c/d.

Here is an implementation of the algorithm in Python. The code takes a number x between 0 and 1 and a maximum denominator size N. It returns the numerator and denominator of the best rational approximation to x using denominators no larger than N.

def farey(x, N):
    a, b = 0, 1
    c, d = 1, 1
    while (b <= N and d <= N):
        mediant = float(a+c)/(b+d)
        if x == mediant:
            if b + d <= N:
                return a+c, b+d
            elif d > b:
                return c, d
            else:
                return a, b
        elif x > mediant:
            a, b = a+c, b+d
        else:
            c, d = a+c, b+d

    if (b > N):
        return c, d
    else:
        return a, b

In Python 3.0, the float statement could be removed since the division operator does floating point division of integers.

Read more about rational approximation in Breastfeeding, the golden ratio, and rational approximation.

Here’s an example of a situation in which you might need rational approximations. Suppose you’re designing an experiment which will randomize subjects between two treatments A and B. You want to randomize in blocks of size no larger than N and you want the probability of assigning treatment A to be p. You could find the best rational approximation a/b to p with denominator b no larger than N and use the denominator as the block size. Each block would be a permutation of a A’s and b-a B’s.

Update 1: Here is a form that implements the algorithm above.

Update 2: Eugene Wallingford wrote a blog post about implementing the algorithm in Klein, a very restricted language used for teaching compiler writing.

The fastest ways to test whether a number is prime have some small probability of being wrong. Said another way, it’s easier to tell whether a number is “probably” prime than to tell with certainty that it’s prime. This post looks briefly at algorithms for primality testing then focuses on what exactly it means to say a number is “probably prime.”

[click to continue...]

Paul Erdős had this notion that God kept a book of the best proofs. Erdős called God’s book simply “the book.” Springer recently published Proofs from THE BOOK, a collection of elegant proofs that the authors suppose might be in God’s book.

For many mathematicians, the first proof that comes to mind as a candidate for a proof in the book is Euclid’s proof that there are infinitely many primes. The proof is so short and simple that it can almost be written within the 140-character limit of Twitter. I give the proof in my AlgebraFact Twitter account as follows.

There are infinitely many primes. Proof: If not, multiply all primes together and add 1. Now you’ve got a new prime.

Several people pointed out that I was a little too terse. If N is the supposed product of all primes + 1, N itself doesn’t have to be a new prime. It could be that N has a factor that is a new prime. The smallest prime factor of N must be a prime not on the list. Either way “you’ve got a new prime,” but the proof above leaves out some important details.

Here’s an example. Suppose we believed the only primes were 2, 3, 5, 7, 11, and 13. Let N = 2*3*5*7*11*13 + 1 = 30031. Now N cannot be divisible by 2, 3, 5, 7, 11, or 13 because there is a remainder of 1 when dividing N by any of these numbers. Maybe N is a new prime, or maybe N is composite but N has a prime factor not on our list. The latter turns out to be the case: 30031 = 59*509.

If you can find a better summary of Euclid’s proof in 140 characters or less, please leave it in the comments. Please include the character count with your proposal.

Related posts:

In praise of tedious proofs
Proofs of false statements

An integer is either a perfect square or its square root is irrational. Said a different way, when you compute the square root of an integer, there are either no figures to the right of the decimal or there are an infinite number of figures to right of the decimal and they don’t repeat. There’s no middle ground. You can’t hope, for example, that the decimal expansion might stop or repeat after a hundred or so terms.

This theorem came up recently when I was talking to one of my kids about her math class, so I decided to look up the proof. It’s easier than I expected, not much harder than the familiar proof that the square root of 2 is irrational. Here goes.

Suppose a/b is a fraction in lowest terms, i.e. a and b are relatively prime, and a/b a solution to xⁿ = c where n > 0 is an integer and c is an integer. Then

(a/b)ⁿ = aⁿ / bⁿ = c

and so

aⁿ / b = c b^n-1.

Now the right side of the equation above is an integer, so the left side must be an integer as well. But b is relatively prime to a, and so b is relatively prime to aⁿ. The only way aⁿ / b could be an integer is for b to equal 1 or -1. And so a/b must be an integer.

This proof shows that what we said about square roots extends to cube roots and in fact to all integer roots. For example, the fifth root of an integer is either an integer or an irrational number.

Update: Note that there’s another proof in the comments, one that I believe is easier to follow.

Suppose you’re waiting for a friend and you have nothing to do. After a few minutes of boredom you pick up a pencil and some scrap paper. You start listing the prime numbers.

2, 3, 5, 7, 11, 13, 17,19, 23, 29, 31, …

Next you write down the forward differences, subtracting each number in the sequence from the one that follows it.

1, 2, 2, 4, 2, 4, 2, 4, …

Your friend is running late and so you repeat the process starting with the sequence you just created.

1, 0, 2, -2, 2, -2, 2, 2, 4, …

Hmm. That time you got a negative number in the list. You’re just doodling and you don’t want to think too hard, so you decide you’ll ignore signs and just write down the absolute values of the differences. So you erase the negative sign and take differences again.

1, 2, 0, 0, 0, 0, 0, 2, …

Your friend is quite late, so you keep doing this some more. After a while you notice that every new sequence has started with 1. Will every sequence start with 1? That’s Gilbreath’s conjecture, named after Norman Gilbreath who asked the question in 1958. I ran across the conjecture in The Math Book by Clifford Pickover. Gilbreath wasn’t the first to notice this pattern. François Proth noticed it in 1878 and published an incorrect proof of the conjecture.

Gilbreath’s conjecture has been verified for the first several billion sequences, but nobody has proved that every sequence will start with 1. Paul Erdős speculated that Gilbreath’s conjecture is true but it would be 200 years before anyone could prove it. I find Erdős’s conjecture more interesting than Gilbreath’s conjecture.

Here’s what I imagine that Erdős had in mind. While the process Gilbreath created is very simple, it is also a strange thing to study. It’s not the kind of thing that people have proven theorems about. No one knows how to approach the problem. There are far more complicated problems in the mainstream of mathematics that will probably be resolved sooner because they are related to previously solved problems and researchers have some idea where to start working on them.

Other posts on number theory:

Constructive proof of the Chinese remainder theorem
How to solve linear congruences
How many numbers are squares mod m
Connecting probability and number theory

Other posts on proofs:

Why proof by examples doesn’t work
Errors in math papers not a big deal?
Jenga mathematics
In praise of tedious proofs
Proofs of false statements

Quadratic congruences are much more complex than linear congruences. If you’re interested in the details, see these notes on quadratic congruences.

When I started looking into this, I thought my number theory class years ago covered the details but that I’d forgotten them. Looking back, I see that my instructor and my textbook neglected some cases. Then I looked at a few other references and saw that they also left out some cases. I put together some notes by pulling together information from several incomplete but complementary references.

The Chinese Remainder Theorem (CRT) is a tool for solving problems involving modular arithmetic. The theorem is called the “Chinese” remainder theorem because the Chinese mathematician Sun Tsu stated a special case of the theorem sometime between 280 and 473 A.D. In its simplest form, the theorem says that if you want to solve a congruence (mod α β), you can solve it (mod α) and (mod β) separately, then combine the solutions to these sub-problems into a solution to the original problem, provided α and β are relatively prime.

More generally, the CRT says that the system of equations x ≡ a_i (mod m_i) has a common solution if the numbers m₁, m₂, …, m_r are relatively prime in pairs (i.e. m_i and m_j have no factors in common if i ≠ j). The solution is unique mod m where m is the product of the m_i’s. In a typical application, you may start with a problem stated (mod m) and then factor m into prime powers. Each of these prime powers is then an m_i in the CRT. For example, to solve a congruence (mod 1400), you might set m₁ = 8, m₂ = 25, m₃ = 7.

You can find an existence proof of the Chinese Remainder Theorem in any number theory book. Here I present an explicit solution given in Donald Knuth’s book Seminumerical Algorithms. For other algorithms and much more information on the CRT, see the book Chinese Remainder Theorem: Applications in Computing, Coding, and Cryptography. (In case it seems “coding” and “cryptography” are redundant, the book uses “coding” to refer to error-correcting codes, such as the way music is encoded on a CD, not secret codes, which would fall under cryptography.)

First we find numbers y_i such that y_i ≡ 1 (mod m_i) and y_i ≡ 0 (mod m_j) for i ≠ j. Then the sum a₁ y₁ + a₂ y₂ + … + a_r y_r is the solution we’re looking for.

But how to find the y_i? We can let y_i = (m/m_i)^φ(m_i).

But what is φ and why does this work? The function φ is called the Euler phi function. For a positive integer n, φ(n) is the number of positive integers less than n and relatively prime to n. (I’ll explain how to compute it in a minute.) Euler proved that if two numbers a and n are relatively prime, then a^φ(n) ≡ 1 (mod n). Because m/m_i is relatively prime to m_i, y_i ≡ 1 (mod m_i). For j ≠ i, m/m_i is a multiple of m_j and so y_i ≡ 0 (mod m_j).

So how do you compute φ(n)? This is easy once you know two facts about this function. First, if α and β are relatively prime, then φ(α β) = φ(α) φ(β). Second, for a prime p, φ(p) = p-1 and φ(p^k) = p^k – p^k-1 for k > 1. Putting these facts together, you can easily calculate φ(n) once you have its factorization into prime powers.

The solution given here is not be the fastest way to compute a solution to the problem posed by the CRT, but it is interesting because it’s explicit. On the other hand, it’s not terribly inefficient. The term (m/m_i)^φ(m_i) can be calculated using no more than 2 log₂φ(m_i) multiplications using fast exponentiation.

Related posts:

How to solve linear conguences
How to solve quadratic congruences

How do you efficiently compute aⁿ for integer n? You could multiply a*a*a*…*a, n-1 multiplications, but there are much more efficient ways. For example, a⁸ could be computed by ((a²)²)² in three multiplications. This example suggests it may be worthwhile to think about the binary representation of the exponent.

Here’s an algorithm. Write the exponent n in binary. Read the binary representation from left to right, starting with the second bit from the left. Start with the number a, and every time you read a 0 bit, square what you’ve got. Every time you read a 1 bit, square what you’ve got and multiply by a. It follows that aⁿ can be computed using no more than 2 log₂(n) multiplications.

As an example, suppose we want to calculate 7¹³. In binary, 13 is written as 1101. We skip over the leading 1 then read 1, 0, and 1. So we calculate ((((7²)7)²)²)7. In C notation, we would compute as follows.

x = 7;
x *= x;
x *= 7;
x *= x;
x *= x;
x *= 7;

In number theory calculations, such as arise in cryptography, it’s often necessary to compute aⁿ (mod m) for very large integers a, n, and m. These numbers may be hundreds or thousands of digits long and so of course the calculations cannot be carried out using ordinary machine integers. You could compute aⁿ first then reduce the result (mod m), but it would be more efficient to reduce (mod m) after every multiplication. This puts an upper bound on the size of numbers (and hence the amount of memory) needed for the calculation.

The same algorithm works when a is not an integer but a matrix. For example, consider a large matrix M that gives the connections between notes in a graph. M contains a 1 in position (i, j) if the i^th and j^th nodes are connected by an edge and contains a 0 otherwise. The n^th power of M tells which nodes are connected by paths of length less than or equal to n. If M is large, we don’t want to do unnecessary multiplications in computing Mⁿ.

For some exponents, the method given above can be improved. The smallest exponent for which you can improve on the binary algorithm is 15. Using the binary algorithm, computing a¹⁵ requires six multiplications. But you could compute the same quantity in five multiplications as follows.

b = a*a*a;
c = b*b;
c *= c;
c *= b;

For more examples, see Seminumerical Algorithms section 4.6.3.

A linear congruence is the problem of finding an integer x satisfying

ax ≡ b (mod m)

for specified integers a, b, and m. This problem could be restated as finding x such that

1. the remainder when ax is divided by m is b,
2. a*x % m == b in C code,
3. ax – b is divisible by m, or
4. in base m, ax ends in b.

Two solutions are considered the same if they differ by a multiple of m. (It’s easy to see that x is a solution if and only if x + km is a solution for all integers k.)

For example, we may want to solve 7x ≡ 3 (mod 10). It turns out x = 9 will do, and in fact that is the only solution. However, linear congruences don’t always have a unique solution. For example, 8x ≡ 3 (mod 10) has no solution; 8x is always an even integer and so it can never end in 3 in base 10. For another example, 8x ≡ 2 (mod 10) has two solutions, x = 4 and x = 9.

In this post, we answer two questions.

1. How many solutions does ax ≡ b (mod m) have?
2. How can we compute them?

The answer to the first question depends on the greatest common divisor of a and m. Let g = gcd(a, m). If b is not divisible by g, there are no solutions. If b is divisible by g, there are g solutions.

So if g does divide b and there are solutions, how do we find them? The brute force solution would be to try each of the numbers 0, 1, 2, … m-1 and keep track of the ones that work. That works in theory, but it is impractical for large m. Cryptography applications, for example, require solving congruences where m is extremely large and brute force solutions are impossible.

First, suppose a and m are relatively prime. That is, assume g = gcd(a, m) = 1. We first put the congruence ax ≡ b (mod m) in a standard form. We assume a > 0. If not, replace ax ≡ b (mod m) with -ax ≡ -b (mod m). Also, we assume a < m. If not, subtract multiples of m from a until a < m.

Now solve my ≡ -b (mod a). This is progress because this new problem is solving a congruence with a smaller modulus since a < m. If y solves this new congruence, then x = (my + b)/a solves the original congruence. We can repeat this process recursively until we get to a congruence that is trivial to solve. The algorithm can be formalized into a procedure suitable for programming. The result is closely related to the Euclidean algorithm.

Now what if the numbers a and m are not relatively prime? Then first solve the congruence (a/g)y ≡ (b/g) (mod (m/g)) using the algorithm above. Then the solutions to ax ≡ b (mod m) are x = y + tm/g where t = 0, 1, 2, …, g-1.

Here are a couple examples.

First, let’s solve 7x ≡ 13 (mod 100). Since 7 and 100 are relatively prime, there is a unique solution. The algorithm says we should solve 100y ≡ -13(mod 7). Since 100 ≡ 2 (mod 7) and -13 ≡ 1 (mod 7), this problem reduces to solving 2y ≡ 1 (mod 7), which is small enough to solve by simply sticking in numbers. We find y = 4. Then x = (100*4 + 13)/7 = 59. You can verify that 7*59 = 413 so 7*59 ≡ 13 (mod 100). In general, we may have to apply the algorithm multiple times until we get down to a problem small enough to solve easily.

Now let’s find all solutions to 50x ≡ 65 (mod 105). Since gcd(50, 105) = 5 and 65 is divisible by 5, there are 5 solutions. So we first solve 10x ≡ 13 (mod 21). The algorithm above says we can solve this by first solving 21y ≡ -13 (mod 10), which reduces immediately to y ≡ 7 (mod 10), and so we take y = 7. This says we can take x = (105*7 + 65)/50 = 16. The complete set of solutions to our original congruence can be found by adding multiples of 105/5 = 21. So the solutions are 16, 37, 58, 79, and 100.

I intend to write posts in the future about how to solve simultaneous systems of linear congruences and how to solve quadratic congruences.

Update: Here are the posts I intended to write: systems of congruences, quadratic congruences.