That seems to be a good way to look at it with p and q prime. I didn't quite see it that way before.Quote:
Originally Posted by desiresjab
Printable View
That seems to be a good way to look at it with p and q prime. I didn't quite see it that way before.Quote:
Originally Posted by desiresjab
Thanks. I want to unravel each function in this way. What you quoted is what I now consider the nutshell truth about the CRT. Unfortunately, that understanding alone does not allow one manipulative powers in CRT, it just clears the mind of junk associated with wondering what is going on.Quote:
Originally Posted by YesNo
Nor does going from the separate modulii to the combined one mean going backwards is necessarily easy, though I have seen it called trivial. It will take practice, like maneuvers in any enterprise require practice and familiarity. CRT and other functions of number theory have to become muscle memory. Computing backwards in the CRT will be the subject of my next post. It has to be--since I have a hunch I will at first be confused.
This is a central function of number theory, because it is certainly a central theorem of modular arithmetic, and modular arithmetic is central to number theory. People who know what they are doing use it routinely in various applications. There are encryption systems based on it. On computers, calculations involving very large numbers are routinely broken down into smaller units via the CRT and the result obtained using the separate modulii, before converting back to mod pq.
I say all this to justify my staying with the function a while longer, for unless I see plumb through it, I have not seen enough, though the effort is tedious and exhausting for me, as well. Yet, it is the way I always preferred to study math. No way school courses go slow enough for my tastes. There are too many places I want to stop for a month and investigate the way we investigate here, but that luxury is not practical, so Monday they are on to a new topic. Everything is a rush job.
We will turn the CRT inside out like a straitjacket, put it on and take it off unaided at will, as casually as we remove our daycoat upon entering the house. I ask, is there a lesser level of familiarity that would prove satisfactory with a function used constantly in multifarious applications in one's chosen field of study? Unless one can see these applications when they arise in the wild, one is tapping the cane of the blind; and unless one can successfully implement central functions in those situations, one remains in the wild.
What I like to do to improve familiarity is to program the algorithms, to the extent there are algorithms.
Yes, that is a beautiful way to get familiar. Plus, it has fringe benefits.Quote:
Originally Posted by YesNo
Time for the next phase. How much information do we need to work backwards fruitfully? Suppose we are given the naked result of the last problem. What can we do with this result?
x≡187 (mod 420)
x≡ ? (mod 3)
x≡ ? (mod 4)
x≡ ? (mod 5)
x≡ ? (mod 7). These values are easy to fill in.
x≡ 1 (mod 3)
x≡ 3 (mod 4)
x≡ 2 (mod 5)
x≡ 5 (mod 7).
Nothing difficult about that. It appears the only difficulty lies in working the CRT forward, not backwards. Backwards is, as they say, trivial.
Some good news at last!
I agree that going backwards is trivial except it does require being able to factor the larger modulus into a different set of primes.
Now it is time for a simple application.Quote:
Originally Posted by YesNo
Multiply 41 times 43 via the CRT.
Of course we ignore the fact that we know this is equal to 422-1. At some point a highly observant mathematician would notice that the product he was trying to reconstruct (providing he had been given only the system below and not the two numbers to be multiplied)—he or she would notice that the two numbers were two apart anyway. This information would do him no particular good, I suppose. He would merely realize he was working out some T2-1, while the solution to the system was extracted as usual using CRT.
41≡1 (mod 5) 43≡3 (mod 5)
41≡6 (mod 7) 43≡1 (mod 7)
41≡5 (mod 9) 43≡7 (mod 9)
41≡8 (mod 11) 43≡10 (mod 11)
In typical alternate notation: (1, 3), (6, 1), (5, 7), (8, 10)
What we have to do is multiply the quantities I have bolded above.
1·3≡3 (mod 5), 6·1≡6 (mod 7), 5·7≡8 (mod 9), 8·10≡3 (mod 11). That is,
x≡3 (mod 5), x≡6 (mod 7), x≡8 (mod 9), x≡3 (mod 11).
Now all that remains is to solve the system.
3(693)-1 (mod 5)+ 6(495)-1 (mod 7)+ 8(385)-1 (mod 9)+3(315)-1 (mod 11)=
3(693)(2)+6(495)(3)+ 8(385)(4)+3(315)(8)
6(693)+18(495)+32(385)+24(315)≡1763 (mod 3465).
It is hard to believe, after what I had to go through to get this simple product, that this method could actually be shorter and easier in some context. Perhaps mark it down to my half dim understanding of byte mechanics in computers, I suppose. We see that it does work, though, and now we understand the mechanics of multiplication via the CRT.
We had to use numbers far larger than the eventual product to get our product. What is this? How could this be easier for a computer? For a really huge number in this method, I would need a commensurately huge number of terms in the addition. This is crazy. I have to be missing something. Am I?
Notice that in the last problem I chose the modulii to be used in the CRT multiplicaion. I chose 5, 7, 9, 11. None of these have any factors in common with 41 or 43 which are both prime, by design. But suppose I had chosen to multiply two composite numbers such as 88 and 63. It would have been possible to choose some of the modulii that were not relatively prime to 88 or 63 or both, and this is completely okay to do. In fact, I suspect it could be one way of shortening computer run time, since in those terms where the modulii share a factor with a multiplier 0 will be a constant out front for that term in the addition. One could perhaps tailor the modulii so that few computations were needed because most dropped off to zero due to this choice.
That wraps it up for now on the Chinese Remainder Theorem. We know how to solve a system of congruences and we know how to multiply using the CRT. I would not know where to look for more understanding. I think that will have to be encountered in the wild, where we must be ever alert for opportunities to deploy it. This goes for all the basic functions and algorithms of number theory such as
1 The Chinese Remainder Theorem
2 The Euler Phi function
3 Quadratic Reciprocity
4 The DeuceHound Ruler Function
5 Divisor and sum of divisors functions
6 Euclidian algorithm
7 Fermat's little theorem (generalized for composites as well)
8 Wilson's Theorem
9 Discrete Logarithms
10 Primite Roots
11 Modular power series
12 Properties of Congruences
This list can only grow. However, mastery of the above is a good idea for any serious student of number theory.
I have an idea for a graphically oriented computer program. Very simple--a number line stretching to the far reaches of cardinality. Marked on the line are all powers greater than 1 of every integer. As the viewer travels farther out the line at an adjustable speed, he is able to stop the progress where any two powers are relatively close together and examine the actual numbers on the line, then resume rushing outwatrd again. Quite simple. One could have a background of stars and eerie music suggestive of infinity. My own investigations (limited by thirty-two bit precision) indicate that the powers grow ever farther apart as we proceed outward, despite there being more of them the farther out we go. I do not have any sources and I do not know exactly how to approach the problem of calculating the distance between powers. Perhaps there is a rule. Some approximate formula would probably be the hope, if there was any hope, I mean to say.
Here is a short link on the subject. One is reminded of the formulas for irrationality measure, and that is even brought up in one of the posts. Of course this is only concerned with powers of 2 and 3, where my question more generally involves powers of all integers at once.
http://mathoverflow.net/questions/11...nd-powers-of-3
The irrationality measure reminds me the Liouville questions we discussed earlier.
That is what I meant. It reminded me of the same thing. Which is something I definitely have to get back to. But first things first. Why did I not already know that iteration of Euler's ф function eventually produces a power of 2, and from there on out power's of 2 exclusively?Quote:
Originally Posted by YesNo
I can see why powers of 2 do it, once it gets that far, but I do not immediately see why iterations of any number always devolve to a power of 2. I was just messing around with a ф calculator online. I put in a really huge number of the variety100...0001, looking for a big prime to begin with. I did not find one, but ф was usually about half the value of the iterated N, it seemed, once the function got cranking for a few iterations, and eventually it was always half. I do not have any information about how many steps it takes for this to occur. It seems like something that would have been figured out already. A little thought might reveal the answer intuitively. I hate to think too hard. What do you say about this?
Well, scratch that observation about the ф function. It was wrong. I think I am glad. Amateurs are often led astray and given to much ado about nothing, until a little more investigation reveals their haste.
I hate to keep correcting myself. I think I got sleepy and confused one investigative result with another. I do believe repeated iteration of the Euler ф function eventually yields a pure power of 2 in its chain for any whole number whatsoever, and of course from there on out, all powers of 2. It only takes one counter example.
Actually, it occurs to me now that if one proved the ф function was always even (excluding the very last iteration), that would prove the iterations must eventually descend to a power of 2. What makes me curious is that the function values seem to descend to a pure power of 2 long before they have to in the sense I just described. Many large arguments arrive at a pure power of 2 on a quite large one. 1000000, on the other hand, did not arrive until 4096.