The Remainder Sequence, Part 1
Friday August 18, 2006 by Noam Samuel
Well, as promised, I am here to write about the remainder sequence and its implications. In this article, I’ll pick up on the first question. Is the remainder sequence of a number unique per that number, or are there two numbers that hold the same remainder sequence?
Well, we can start off by saying that if I begin with any the number n, we know that if the remainder of n+m by division of x (also called n+m mod x) then m is divisible by x.
From then on, we can go to say that if we want to add a number x to another number n such that the remainders of x+n by division of all the prime numbers smaller than x will be equal to the remainders of x be division of all the primes smaller than x, n would have to be divisible by all primes smaller than x.
Now, since all primes are coprime (have a greatest common divisor of 1), we know that the smallest number divisible by all primes before x is their collective product. This is because of a little thing called the fundamental theorem of arithmetic (again, I’m going to let you figure out how that one works).
But wait! Suppose we take the product of all primes smaller than x and subtract 1 from it, we will now get a number that cannot be divisible by any prime smaller than x, and thus must be a prime in of itself, or divisible by two or more new primes that exist between the largest prime smaller than x and the multiple of all primes smaller than x.
Now, it doesn’t take much to understand that if p is the product of all primes smaller than x, then p By now you must ask “how does all this connect back to the Remainder Sequence”? Well, now comes your time. In case you have forgotten, the remainder sequence is the sequence of the remainders by division of x for all primes smaller than x for any number x. Now, since we now know that the smallest number that has the same remainder sequence as x does up to the remainder by division of the largest prime smaller than x is x+p, where p is the product of all primes smaller than x, and that there must be another prime between x and x+p (how do we know that it must be larger than x? The answer is surprisingly circular: we were discussing all the primes smaller than x, and thus the new prime cannot be smaller than x), we also know that, since there must be an additional element in x+p’s (and in all subsequent numbers’) remainder sequence, its remainder sequence (and that of all subsequent numbers) must be different. Thus, there cannot be any number larger than x which has the same remainder sequence. Since this applies to all numbers, this means that the remainder sequence must be unique per every number. QED. P.S.
You still haven’t answered my challenge: Can you construct a method to convert between two bases and prove that it works? I’m still waiting. Oh, and participation by writers in The Math Underground is prohibited.