If $n\nmid a,a+d,a+2d. . . a+(n-1)d$,then $(n,d)=1$

Question

None of the numbers in the sequence $a,a+d,a+2d,a+3d. . . a+(n-1)d$ are divisible by $n$.Then we have to prove that d and n are coprime.

I am supposed to use the pigeonhole principle for this problem.Looking at the equation mod n leads us to finding that the last term is just $a-d$ mod n.But that does not help me go further.I think we are going to use the coefficients of d somewhere,along with the number of remainders.A hint will be appreciated.

Answer 1

Suppose $(n,d) = 1$.

Then the classes of $ \{\ a,a+d,a+2d. . . a+(n-1)d\ \} $ $\mod(n)$ are all different because if $$n \mid a +hd - (a +kd) \Rightarrow n \mid (h-k)d$$ with $(h-k) < n$ and so $(n,d) \neq 1 $.

But the classes $ \{\ a,a+d,a+2d. . . a+(n-1)d\ \} $ are $n$ and so one is the zero class, for example $a + ud \equiv 0 \mod n \Rightarrow n \mid a + ud $ and this is a contradiction