# Modular Arithmetic question, possibly involving Chinese remainder theorem

‘6 professors begin courses of lectures on Monday, Tuesday, Wednesday, Thursday, Friday and Saturday, and announce their intentions of lecturing at intervals of 2,3,4,1,6,5 days respectively. The regulations of the University forbid Sunday lectures (so that Sunday lecture must be omitted). When first will all six professors find themselves compelled to omit a lecture?’

This is the question I’m struggling with, I believe it can be solved using the Chinese Remainder theorem, but am really going no where with it. Any progress I make I will post, but I have not yet done anything worth adding to this. Any help would be greatly appreciated!

EDIT: Ok, so I have reduced the problem down to finding the minimum positive value such that, d=11(mod 12), 6(mod 5), 0(mod 7).

#### Solutions Collecting From Web of "Modular Arithmetic question, possibly involving Chinese remainder theorem"

Let the number $1$ label the first Monday. Then the professors’ schedules mean that their lecturing days satisfy the congruences below:
\begin{align*} d_1&\equiv1\pmod2,\\ d_2&\equiv2\pmod3,\\ d_3&\equiv3\pmod4,\\ d_4&\equiv4\pmod1,\\ d_5&\equiv5\pmod6,\\ d_6&\equiv6\pmod5. \end{align*}
In order to find the Sunday in which the last professor is forced to refrain lecturing, we will take the minimum positive solution to each system $d_i=i\pmod\circ$, $d_i=0\pmod 7$ (so that professor $i$ should be lecturing by the schedule but can’t because it’s Sunday) and find the maximum among them. I just checked multiples of $7$ mentally until I found solutions to each. The solutions are $7,14,7,7,35,21$, so by $35$ days every professor will have omitted a lecture at some point.

On the other hand, if you’re looking for the first Sunday in which all six professors simultaneously omit a lecture, then we must solve all of the above congruences for a single $d$ at the same time, with the additional congruence of $0\bmod7$. Note that the modulo $1$ congruence is trivially satisfied and can be thrown out, the modulo $2$ congruence gets subsumed into the modulo $4$ congruence and the modulo $3$ congruence gets subsumed into the modulo $6$ congruence, so reducing gives $d\equiv$
\begin{align*}3&\bmod4,\\5&\bmod6,\\1&\bmod5,\\0&\bmod7.\end{align*}
The first two can be solved into $11\bmod12$, leaving the remaining modulus’s coprime so that you can use the general construction method from Wikipedia’s article on the Chinese remainder theorem in order to solve this system. The computation is
$$11\cdot35\cdot(35_{12}^{-1})+1\cdot84\cdot(84_5^{-1})=4571\equiv371\bmod420$$
hence our solution is day 371. (But what crazy classes take over a year nonstop?)

Luckily seven is a prime, so all the professors will need to skip every seventh lecture. Let the coming Sunday be number zero, let $i$ be the Sunday $i$ weeks into the future, and let $N$ denote the number of a Sunday, on which they all need to skip a class. Prof. Monday will need to skip this Sunday and every second Sunday thereafter, so $N\equiv 0 \pmod 2$. Prof. Tuesday would first like to preach on Sunday $\#1$ exactly $12=4\cdot3$ days after his course commences, so $N\equiv 1\pmod 3$. Prof. Wednesday will miss an opportunity on the coming Sunday as well, so $N\equiv 0\pmod 4$. The eager beaver prof. Thursday will be irritated on every single Sunday, and can thus be left out of the reckoning. The lazy professor Friday will first be annoyed (or relieved?) on Sunday $\#4$ (four full weeks plus two days from Fri to Sun = $30=5\cdot 6$ days), so $N=4\pmod 6$. Professor Saturday’s first miss is $15=3\cdot5$ days after his course has started on Sunday $\#2$, so $N\equiv 2\pmod 5.$

BUT I’m not going to solve this for you. Check the above, and then use the CRT to find the possible values of $N$. For extra credit you should observe that it was not a priori clear that the six professors would all miss a lecture on the same Sunday. A number of miraculous fits occurred, so I give some due credit to whoever composed this problem.

HINT $\$ It’s easy since $\rm\ n\equiv -1\$ for almost all moduli. Therefore, for example

$$\rm\qquad\ \ n \equiv -1\ \ (mod\ i,\:j,\:k)\ \ \Rightarrow\ \ n\equiv -1\ \ (mod\ \ lcm(i,j,k))$$

Said in more elementary terms $\rm\ \ i,\:j,\:k\ |\ n+1\ \ \Rightarrow\ lcm(i,j,k)\ |\ n+1$

So you can replace most of the Chinese Remainder calculation by much simpler $\rm\:lcm\:$ calculations. One can perform the same optimization in any CRT problem where the values are the same for more than one modulus, i.e. where the solution has “constant” value, e.g. $\rm\:n\:$ is constant $\rm\equiv -1\:$ for all three moduli above. For another example of analogous CRT optimization see this answer, where the above optimization simplifies a three-page calculation to a trivial three-line calculation.

If you want to use the Chinese Remainder Theorem, you must number the days starting with the first lecture on Monday; then to find the Sunday when they all omit a lecture, you find the number of the day that it lands on. Now you can use arithmetic.

The given conditions on 1) the days that the professors start and 2) the intervals between their lectures show that the day numbers on which each professor lectures will satisfy a congruence condition. Sundays satisfy another congruence condition. You need the smallest positive solution of all of these congruences, and one way to solve them is to use the constructive proof of the CRT. However, I think a faster and simpler solution will combine some trial-and-error with the statement of the CRT to show that the solution you found is the smallest one.

The answer can be further simplified : 371 (mod 420) = 371 (mod 420 ÷2) = 161 (mod 210). On the (161 ÷7=) 23rd Sunday when all 6 profs are compelled to omit a lecture.
Remark:
if keep x = 1 (mod 2) and x= 2 (mod 3) instead of the equivalent x = 3 (mod 4) = 3 (mod 4÷2) =1 (mod 2), x = 5 (mod 6) = 5 (mod 6 ÷2) = 5 (mod 3) = 2 (mod 3), resp., then you would get directly : x = 161 (mod 210).
See: https://tomcircle.wordpress.com/2017/01/05/crt-problem/