Strange counters (Residue Number Systems)

This video explains Residue Number Systems (RNS). The usual way to define RNS is as follows: We choose n integers (a1,a2,...,an) greater than 1 such that they are relatively prime (no shared prime factors). The Chinese Remainder Theorem says that each number x in the range 0...a1*a2*...*an has a unique set of residues (x%a1,x%a2,...,x%an). The proof for addition and multiplication is as follows: Say a number x has x%5 = n. So x=5a + n for some integer a. Similarly if y has y%5 = m, then y = 5b + m. So x + y = 5a + 5b + n + m. And (x + y) % 5 will cause all the multiples of 5 to drop, and we are left just with (n + m) % 5. Similarly for multiplication, we'll get x * y = 25ab + 5ma + 5nb + nm and again % 5 will leave just (nm) % 5. Regarding the comment at 13:52: Let's start with the (5,7,3) counter showing (1,0,0). We are looking for a number x such that x%5=1 and x%7=0 and x%3=0. Satisfying the last two requirements is easy: x=7*3=21 will obviously satisfy x%7=x%3=0. In this case, it also satisfies x%5=1, but this is a coincidence.  Now the (5,7,3) counter showing (0,1,0). Again, x=5*3=15 will satisfy x%5=x%3=0. And again, we're lucky to have x%7=1. Finally, the (5,7,3) counter showing (0,0,1). Here, x=5*7=35 satisfies x%5=x%7=0. But we're out of luck: x%3=2 and not 1 as we need. We know however that to satisfy x%5=x%7=0 then x must be a multiple of 35. In the range 0...105 there is only one more option: x=2*35=70, which satisfies x%3=1 as well. Generally however, with larger moduli, searching like this can be tedious. So here's the general, efficient algorithm: Let M be the size of the wheel that shows 1. And N1,N2,...,Nk be the sizes of the wheels that show 0, and N=N1*N2* . . . *Nk their product. M and N share no prime factors. According to a known result in number theory, because M and N share no prime factors, then the equation N*a+M*b=1 has a solution where a and b are integers. Note that the equation N*a+M*b=1 is in regular arithmetic, not modular arithmetic. For example, if M=5 and N=21, then 21a+5b=1 can be solved with a=1 and b=-4. Also, there's an efficient algorithm, called the Extended Euclidean Algorithm, that is given N and M and it finds a and b. This is useful for us, because x=N*a satisfies all the requirements we need: * N is the product of the sizes N1, N2,..,Nk Therefore x%N1=(N*a)%N1=0, and similarly x%N2=x%N3= . . . =0. * Rearranging the terms, we get that x=N*a=1-N*b. This means that x%M=(1-M*b)%M=1,  (because the %M operation drops all multiples of M),  and so the size-M wheel shows 1. Music ID: 1YYBAL9DCELLYTIS