Question

(A) Over 1000 students organized to celebrate running water and electricity. To count the exact number of students protesting, the chief organizer lined the students up in columns of different length. If the students are arranged in columns of 3, 5, and 7, then 2, 3, and 4 people are left out, respectively. What is the minimum number of students present? Solve it with Chinese Remainder Theorem. (B) Prove that for n> 1, if 935 = 5 x 11 x 17 divides n80 – 1, then 5, 11, and 17 do not divide n.

Answer 1

A). x = 2 (mod 3)
`$\mu = 3* 5 * 7 = 105$`

x = 3 (mod 5)
`$y_1=35^(-1) (\mod 3)$`

x = 4 (mod 7)
`y_1=2`

`$y_2=21^(-1)(\mod5) = 1$`

`$y_3=15^(-1)(\mod7) = 1$`

`$x=2 * 35 * 2 + 3* 21* 1+4* 15* 1$`

`=140+63+60`

`=263`

≡ 53(mod 105)

Hence the solution is 105 k + 53 > 1000 for k = 10

Therefore, the minimum number of students = 1103

B).
`$\phi (935) = 640$`

By Eulu's theory

`$935 | a^(640)_n -1$` if n and 935 are coprime.

Now,
`$935|n^(80)-1$` and 80 x 8 = 640

`$935|n^(640)-1$` ⇒ g(n,935) = 1

⇒ 5, 11, 17 do not divide n