Printable View
I do not know what to look into next. I hate being stuck between projects worse than being stuck on a project. When this happens it is best to go study until a relevant project suggests itself. It helps to have a Brocard or suspected Brocard connection.
Time to go to school, folks, for me, that is. I write my own lessons, gleaned from various sources for ideas. I hope you will audit the class. My knowledge of number theory is a patchwork rather than a logical procession up the heirarchy of concepts. I continually find it necessary to backtrack and learn things I missed in my initial excitement to forge ahead. I usually also find it necessary to revisit sites of conflict more than once before concepts sink in. Often, I am satisfied for the moment to glean an important idea of the concept that was easier than I thought it would be, whereupon I will once again set out for amateur waters where actual work (as in absorbing concepts fully) is done in a leisurely fashion more in accordance with sloth. The current topic is such an area of Congruence theory. I have a mediocre understanding of it, now it is time for a complete understanding.
The main idea of the Chinese Remainder Theorem is not hard to understand. It has an analogy in normal algebra—solving a system of equations. Here we solve a system of congruences. This means you will have different modulii. The task is find one modulus that works for everything and solve for n. This turns out to be a delightfully easy concept—you just multiply the various modulii together for the common modulus. The restriction on this is the modulii have to be relatively prime pairwise. This means any two you choose will be relatively prime.
Now, solving a setup problem does not mean one can see everything a theorem implies. Far from it. Learning to see the relvance of basic number theoretic functions in live situations is the more important part of learning them, and comes with experience. After we see how to solve a basic setup problem in this field, we will take a look at something the theorem implies which would have been quite, quite hard to forsee. One would really have to have an instinct for numbers to see this out of the blocks. First, a typical setup type problem.
In a system of linear congruences I could choose my numbers congruent in each modulus at random, and the theorem still guarantees solutions in integers.
* * * * *
Problem:
Find a number n such that when divided by 3 leaves a remainder of 2, when by 5 leaves a remainder of 1, and when divided by 7 leaves a remainder of 1.
This implies that
35n≡70 (mod 140)
28n≡28 (mod 140)
20n≡20 (mod 140)
n would equal 21n-20n, right? It so happens we can set this up. We have
3(35n-28n)=21n
3(70-28)-20=106 (mod 140)=
210-84-20≡106 (mod 140)=
Any number in the same residue class as 106 (mod 140) is a valid solution.
* * * * *
Okay, very cool. Now, what does such a theorem imply that we might not necessarily see right away? What animal would think it means we can solve the following?
Problem:
Can one find one million consecutive integers that are not square free?
Yes, that is how I see it as well, but the idea of "close" is different. If we pick a real number, x, and an arbitrarily small but greater than zero value, epsilon, then there are infinitely many rational numbers (p/q where p and q are integers) close to that x no matter what x we pick. That is |x - p/q| < epsilon for infinitely many values p/q.Quote:
Originally Posted by desiresjab
So that idea of closeness isn't going to help differentiate rational from algebraic or transcendental numbers since there are infinitely many rationals close to any real number.
One way out of the problem is to let epsilon vary depending on the rational number, p/q. If we replace the constant epsilon with a function of the rational number we could get something like |x - p/q| < f(p/q) = 1/q. This would allow epsilon to vary, but it is still not adequate. There are still infinitely many rational numbers close to any real number, x.
One way to tighten the function is to raise q to some power. If we replace f(p/q) = 1/q1 with f(p/q,u) = 1/qu then if u > 1, according to Wikipedia, I don't quite see it yet, only finitely many rationals could approach any given rational number. If u > 2 then we can say that only finitely many rationals approach even irrational algebraic numbers. If that is the case, then we could use this to distinguish between rationals and irrationals and between irrational algebraic and transcendental numbers. We could define a function of x that gives the precise u value back for which the change occurs between having infinitely many rationals approximate x using this new idea of closeness to having only finitely many rationals approximate it.
That will take a lot of thought to reason out. I read your post only once because I am tired. I only partially understood. The idea of a number only being approached by finitely many rationals is foreign to me, which is not bad but hard.Quote:
Originally Posted by YesNo
All numbers have infinitely many rationals within any interval around them. What makes the set finite is that there is an extra constraint on the rational numbers, p/q. Not only must they be close, they must also pass the condition that |x - p/q| < 1/qu where u gets larger than 1. Come to think of it if the Liouville numbers have u arbitrarily large then they will always have infinitely many rational numbers approximating them and fulfilling this new condition. They are an extreme form of transcendental number.
I have to be gone for a few days again. I will be thinking about the Chinese Remainder theorem. There is a less painful way to do it. I am trying to understand the precise logic behind that method. Once you get more than three modulii to work with it is real hard to enact the method I showed earlier, because it requires brain-twisting logic. The new method is more straightforward though a little longer. I will understand it before I present it. Understanding of this method would bring us well along on our goal to a complete comprehension of the CRT. It does not enable us to see how far the influence of the theorem spreads or how many situations that look diverse can be handled by it, but it will be a good start.
Regarding those Liouville numbers, it occurred to me that a way to describe these numbers is to say that they are numbers that can be approximated by a sequence of rational numbers whose denominators are positive, but very small.
The Wikipedia article says: A Liouville number can thus be approximated "quite closely" by a sequence of rational numbers. https://en.wikipedia.org/w/index.php...ouville_number
The metaphor "quite closely" is misleading. One should always be able to find a sequence of rational numbers that approximates the Liouville number even closer than the sequence used to verify that the number is a Liouville number. The only problem with that closer sequence is the denominators of those rational numbers used in that closer sequence would likely be larger than those in the sequence of rational numbers used to show that the number was a Liouville number.
I have learned the secret of the Chinese Remainder theorem. The key involves mod inverses, which are hardly ever used in the proof, I believe. Do not have time now to explain it to our throngs of readers, but will do so when I return from my travels in about three days.
Learning these basic number theoretic functions inside out is another key to number theory. One cannot know them just so-so. Inside out, so that when one is applicable, you are sure to see it instead of putting in a lot of wasred effort. There is no other way.
So each of these million consecutive integers must have at least one prime to the second power?Quote:
Originally Posted by desiresjab
Yes, no repeated factors in a square free prime factorization.Quote:
Originally Posted by YesNo
I am back, but too beat to do a good exegesis on the Chinese Remainder theorem, or even think of it now. To only half see it would be utter failure, and I think I half see it, so I will be at rest here until I go on. I have allowed myself to be confused. Of course I cannot allow that. Ahem!
On the matter of transcendentals, my mind wanders far into the future to wonder if any theory can exist to locate important ones. So far we have just run into numbers like pi and e, or discovered them in a sense out of data. In calculus ex is the number that has itself for derivative, and pi the ratio of the circumference of a circle to its diameter. The Feigenbaum constant was discovered after iterations in chaos theory were noticed to converge. Might there be a seive invented by advanced minds of the future to strain out useful transcendentals, rather than having to discover each one in action? Maybe the question is crazy. I have no idea what the system of constraints would be, but the constraints of the Liouville number might be an echo of that theory. Not a scientific observation, I know, just futuristic musing.
If no repeated factors are allowed, then we could have only a sequence of three consecutive integers since 4 = 22 divides one of every four consecutive integers.
I was thinking about the DeuceHound. I think the general idea of using only n to find all the prime factors of n! is solvable. That is, one does not have to construct n! and then factor it to get the prime factorization. One can get that from working with n itself. Here is a video on the topic that explains one technique: https://www.youtube.com/watch?v=HkAKM2lfvAA The problem with this technique is that it uses an iterative approach by looping through all the powers of a prime in n rather than a closed form to get the number of factors of a prime in n!.
I have not read the link yet. I am excited about doing so. Lying in bed a few moments ago I was thinking about the DeuceHound, too. It can already take its place among valid and useful number theoretic functions, claiming its own identity because it is based directly on the Ruler Function. The Achilles heel of the DeuceHound and of Legendre's floor function method is their inability to find primes. They are able to manipulate what they are told are primes, they do not find these primes themselves. Any machine for finding primes and manipulating them would necessarily be vast, since finding and testing for primes is the really difficult part. As long as it is told which numbers are prime, the DeuceHound will do fine.Quote:
Originally Posted by YesNo
Storing a list of primes in the computer seems quite crude to me. But that is where the human race is on this job.
I looked at the video in the link and the three that followed it. No surprises. He is using the Floor Function algorithm. It is fast and general. The Deucehound is even faster and easier where pure powers of a prime are factorialized, because it is an explicit formula in those cases and Q is equal to zero. Powers factorialized are something that might be found in problems involving the natural sciences. In case Q does not equal zero, we know how to append the value of Q to our total.
With a non-zero value for Q, is the DeuceHound as fast as the Floor method? It is quite close, I think, and has the advantage of an explicit formula for cases where pure powers are factorialized. The DeuceHound has definite similarities to the Floor Function, but is not exactly the same thing, since the Floor Function is not based on the Ruler Function. One is certainly reminded of it as one figures the value of Q, especially.
I am ready to wrap up the series on the Chinese Remainder theorem. We would be stunned if such a theorem did not exist, it is such a natural consequence. If x divided by p leaveas a remainder of a, and x divided by q leaves a remainder of b, it is hardly surprising that x divided by ab will also leave some unique remainder as well, is it now? That is the simplicity of the theorem in plain English. As ususal, the situation in mathematical notation is more difficult but more precise. But anyone should keep in mind the plain English interpretation of the Chinese Remainder theorem above when studying its mathematical details.
We already looked at a method that sometimes works easily for a system of exactly three modular equations. Later in this post or the next post we will look at the most general method for solving systems of congruences.
The method below is extremely simple for two modulii, which we now digress a moment to cover.
x≡2 (mod 3)
x≡4 (mod 5)
5x≡10 (mod 15)
3x≡12 (mod 15)
5x-10=3x-12. Now simply solve for x.
5x+2=3x
2x=-2
x=-1=14
Indeed 14≡2 (mod 3) and 14≡4 (mod 5).
This method is so easy, I recommend it whenever there are only two equations in the system.
* * * * *
For those cases when we have three or more modulii, we want to show and explain the method that is at the heart of matters and will always work.
x≡a1b1M+.....arbrM(mod M)
...........m1...........mr
Is the general description.
M is all the modulii multipled together. M divided by any mi is M without that mi. The b's are the inverses (mod mi) of
M
mi
The big question is why do we want these inverses, how did they get involved?
You might say they are involved because mathematicians wanted them involved. In order to isolate the various ai's so they can be added (mod M), it is necessary get rid of the terms around them. This is accomplished by multiplying
M
mi by its inverse (mod mi)
* * * * *
Let's do a classic example where I will flat make up the numbers. It involves an old lady from the village riding her bicycle to town with a large bag of eggs to sell who is knocked over. All but 160 of her eggs are broken. The culprit, a clumsy but honest mathematician, offers to reimburse her on the spot for damages. The old lady however, being an odd sort, does not remember how many eggs she had, but she does remember a few other details. When she counted them by 3's, there was one left over; when she counted them by 4's, there were three left over, when she counted them by 5's, there were two left over; when she counted them by 7's, there were five left over. At ten cents per egg, how much did the poor mathematician have to pay the old lady?
Step1
x≡1 (mod 3)
x≡3 (mod 4)
x≡2 (mod 5)
x≡5 (mod 7)
Step 2
140x≡140 (mod 420)
105x≡315 (mod 420)
84x≡168 (mod 420)
60x≡300 (mod 420).
In the first column we have divided 420 by each modulus, and in the second column multipled that times the value of x its original modulus. We must now find the inverses of 140, 315, 168 and 300 in their original modulii.
Step 3
(140)-1 (mod 3)=2,
(315)-1 (mod 4)=3
(168)-1 (mod 5)=2
(300)-1 (mod 7)=6
Step 4
Multiply each Mi by both its original value (ai) under the old modulus, and its mod inverse under the old modulus. This indeed must isolate the ai's so they can be added (mod M).
(140)(1)(2)+(315)(3)(3)+(168)(2)(2)+(300)(5)(6)=
280+2835+672+9000=12787
12787≡187 (mod 420).
160 of her original 187 eggs are unbroken. That means the clumsy professor broke only 27 eggs. At a dime apiece, he owes the old gal a mere $2.70.
* * * * *
This method will always work. We may not be quite through with the theorem, though, for I have found some other articles that even explain it graphically, which I intend to look at.
The important thing, of course, is that we make ourselves able to recognize when particular number theoretic functions are relevant and useful in situations encountered in the wild. Without this ability we are only able to answer prepared questions that are carefully worded to let us know which function we should be thinking about.
Speaking of those little important consequences of theorems which conceal themselves in so many places, I just learned one concerning Fermat's Little Theorem, which, had I known it earlier would have greatly aided my efforts at an original proof of the theorem could I have found a clever, non-circuitous way of proving the egg first without the chicken. Anyway, I think it is quite important and a good illustration of why one must be ever watchful for consequences of the theorems one learns, if one ever hopes to become a master of numbers in the wild. This simple overlooked or at least under appreciated fact is that the theorem offers an alternative way to compute mod inverses when a Є *Zp, for a-1 can be computed as ap-2, since we have a·ap-2=1 by the theorem. Yes, circuituous, but an important fact nonetheless, whether or not it can be used constructively in a valid, original proof of Fermat's Little Theorem.
Now I feel compelled to go back and look at my own work with this new restatement in hand. It is possible I even noticed this before but felt I could not use it precisely because I felt the reasoning would be circuitous--like using a word in its own definition. I do not particularly need to, it is more like a drive to complete something I started and was unable to satisfactorily finish. Practice at proving is one aspect of math I could always use work on. Any function one already knows and can make the connection between is fair game for use in a proof of any theorem, including this old one. My way was a visual demonstration followed by an attempt at algebraic proof. If anything interesting comes of my revisit, I will report.