Having an issue with what exactly b1, b2, and b3 are in the formula: X ≡ b1 * N1 * y1 + b2 * N2 * y2 + b3 * N3 * y3 (mod N), since they do not coincide with any of the previous math.
They start with a ≡ 4 (mod 3), a ≡ 2 (mod 4), and a ≡ 3 (mod 7)… I was expecting the values for b to be 4, 2, and 3.
Can anyone help me understand the values of b in the Chinese Remainder Theorem example? Thanks!
This is a funny one to have in the discrete math section, but then again it’s hard to fence off discrete math since it goes into the weeds often.
But you are right that b_1, b_2, b_3 are 4, 2, 3
I think the biggest thing with these concepts is to step back and not get too caught in the formula at first, try to see the high-level of what it does. Then if you have an example, try to follow through an example with the end goal in mind.
I’ll walk through my process (I didn’t know this theorem but that’s an even better indicator of the discovery process).
Meaning X acts as a sort of universal truth if we have two sets of information (the pairwise coprime set, and some b_i’s which are variable).
To put it in more real life terms, we can think as each of the coprime number as capacities to m different boxes. For each box, we are given a hint (for box_i, b_i items will NOT fit that box).
Meaning, the system of equations is really telling us, there is a single quantity of items, that if you try to stuff them into each box alone, will yield the given remainders. As a bonus we know the range of the number is bound by the product of the coprime numbers (a nice quality to quantify how computationally expensive things might be).
So back to the problem, we have a box1 of capacity 3, box2 of capacity 4, box3 of capacity 7. Somebody came in yesterday and tried to pack exactly a items into box1, they said dang I have 4 left over. They took them all out and tried the same with box2, they said dang i have 2 left over. And so forth. The leftover amount in each attempt is b_i. (so the b’s are leftovers, or remainders)
Now for the solution
a ≡ 4 (mod 3)
a ≡ 2 (mod 4)
a ≡ 3 (mod 7)
N_i is the product of all the coprime numbers except the i’th one. So
N_1 = 28, N_2 = 21, N_3 = 12, from this we know
28 * y_1 ≡ 1 (mod 3)
21 * y_2 ≡ 1 (mod 4)
12 * y_3 ≡ 1 (mod 7)
A little algebra will yield y_1 = 1, y_2 = 1, y_3 = 3
so finally
a = ((4 * 28 * 1) + (2 * 21 * 1) + (3 * 12 * 3)) (mod 84)
(84 is 3*4*7)
which means a = 10. The person was trying to fit 10 items into the boxes.
Now, how does 10 ≡ 4 (mod 3) make sense given the analogy?
It turns out 10 ≡ 4 (mod 3) is the same as 10 ≡ 1 (mod 3). Which can only be know after the fact. I know this breaks the pureness of the analogy but that’s life hahahaha.
So, is it safe to go ahead and report the curriculum as incorrect (once again) for using 3,4,5 as b1, b2, b3 when it was solving the original with 4, 2, 3?
I haven’t worked through this content, but looking at the page you linked to, the "Free Response" question is using a system where b_1, b_2, b_3 are 4, 2, 3 respectively and they are asking for the products N_1, N_2, N_3.
The example they work through under the "Solving a System of Congruences" section is a different system where b_1, b_2, b_3 are 3, 4, 5 respectively.
I don’t think they claimed anywhere in the article that the example they were working through was supposed to be the same system as the Free Response question’s system.
I haven’t tried submitting a response. So, does submitting yield a solution where the numbers are mixed up (in which case it probably is a mistake that needs to be fixed)?
Or, are you talking about the example in the text? If so, I don’t think the article author(s) stated anywhere that they were going to walk through the Free Response system’s solution. The two systems are different.
I think someone updated the curriculum as that was not what was there mere hours ago.
The interactive portion asking for N_1, N_2, and N_3 has the correct answer (28, 21, 12)
@chip4637614057 The curriculum is not wrong here. They give an example, and then offer an exercise to practice with… and then jump back to the example. I will say it is confusing, just not wrong. My guess is they were trying to keep users engaged so they could follow through. But on the other hand this is number theory so maybe that methodology that works for code might not work the same in math (it’s alien to me but I’ll give it some benefit of the doubt).
Regardless of what they’re marking, getting back to the point of the system:
The value of the b’s is allowed to be anywhere in the range anywhere within [0. n_i]. You can pick your own b’s and get a different unique answer just for those, that’s the beauty of the system.
And even better is looking up applications for Chinese Remainder Theory (that is, why study it at all in terms of computer science). There are probably a couple of cryptographic use cases (at least historically).
That’s a general thread (looking up applications) for discrete math. There are very well laid-out calculus courses, abstract algebra courses, etc. But discrete math as a topic is not standardized neatly into intro material course (there’s a lot of variance in what colleges offer at this level). It takes from many different mathematical disciplines. Math for it’s own sake is beautiful, but it’s even more powerful if you are at least aware of where it can be used or why it was developed in a certain direction.