Answer to Question #297635 in Combinatorics | Number Theory for Allan

Question

Six professor begin courses on Monday, Tuesday, Wednesday, Thursday, friday, and Saturday, and announce their intention of lecturing at interval of 3,2,5,6,1and 4 days respectively the regulations of the university forbid Sunday a lecture(so that a Sunday a lecture must be omitted) when first will all six professors find themselves compelled to omit a lecture

Answer 1

If the day in question is the xth (counting from and including the first monday), then $\mathrm{x}=1+2 \mathrm{k}_{1}=2+3 \mathrm{k}_{2}=3+4 \mathrm{k}_{3}=4+\mathrm{k}_{4}=5+6 \mathrm{k}_{5}=6+5 \mathrm{k}_{6}=7 \mathrm{k}_{7}$

where the \mathrm{k} are integers ie

 $(1) \mathrm{x} \equiv 1(\bmod 2),\\(2) \mathrm{x} \equiv(\bmod 3),\\(3) \mathrm{x} \equiv 3(\bmod 4) \\ (4) \mathrm{x} \equiv 4(\bmod 1),\\(5) \mathrm{x} \equiv 5(\bmod 6),\\(6) \mathrm{x} \equiv 6(\bmod 5) \\(7) \mathrm{x} \equiv 0(\bmod 7)$

Of these congruences, (4) is no restriction and (1) and (2) are included in (3) and (5).

Of the two later, (3) shows that $\mathrm{x}$ is congruent to 3,7, or $11(\bmod 12)$ , and (5) that $\mathrm{x}$ is congruent

to 5 or 11 , so that (3) and (5) together are equivalent to $\mathrm{x} \equiv 11(\bmod 12)$ . Hence the problem is that of solving

$x \equiv 11(\bmod 12), x \equiv 6(\bmod 5), x \equiv 0(\bmod 7)$

$\mathrm{x} \equiv-1(\bmod 12), \mathrm{x} \equiv 1(\bmod 5), \mathrm{x} \equiv 0(\bmod 7)$

Here $\mathrm{m}_{1}=12, \mathrm{~m}_{2}=5, \mathrm{~m}_{3}=7, \mathrm{~m}=420, \mathrm{M}_{1}=35, \mathrm{M}_{2}=84, \mathrm{M}_{3}=60$ .

The $\mathrm{n}$ are given

$35 \mathrm{n}_{1} \equiv 1(\bmod 12), 84 \mathrm{n}_{2} \equiv 1(\bmod 5), 60 \mathrm{n} \equiv 1(\bmod 7)$

or

$-\mathrm{n}_{1} \equiv 1(\bmod 12),-\mathrm{n}_{2} \equiv 1(\bmod 5), 4 \mathrm{n}_{3} \equiv 1(\bmod 7)$

and we can take $\mathrm{n}_{1}=-1, \mathrm{n}_{2}=-1, \mathrm{n}_{3}=2$ . Hence

 $\mathrm{x}=(-1)(-1) 35+(-1) 1.84+2.0 .60=-49 \equiv 371(\bmod 420)$

The first $\mathrm{x}$ satisfying the condition is 371 .