problem 1

Assume n divides a(k)(a(1)-1).

Write n as p(1)^q(1) * p(2)^q(2) * … * p(m)^q(m). p(i) is a prime number.

For any i, if p(i)^q(i) doesn’t divide a(1)
Then p divides a(2)-1
Then p doesn’t divide a(2)
Then p divides a(3)-1
Then p doesn’t divide a(3)
…
Then p doesn’t divide a(1).

So for any j, if p(i) divides a(j) then p(i)^q(i) divides a(j).

Next, it’s easy to see that if there exists a j0 such that p(i) divides a(j0) then for any j, p(i) divides a(j). Therefore, p(i)^q(i) divides a(j) for all j.

Similarly, if there exists a j0 such that p(i) doesn’t divide a(j0), then for any j, p(i) divides a(j)-1. Therefore, p(i)^q(i) divides a(j)-1 for all j.

So n can be rewritten as x*y. x is the part that divides all a(j); y is the part that divides all a(j)-1.

So we have x divides a(1) and a(2), y divides a(1)-1 and a(2)-1.

So x divides a(1)-a(2) and y divides a(1)-a(2)

Then n=x*y divides a(1)-a(2).

Since both a(1) and a(2) < n. This implies a(1)=a(2). Contradiction.