1
$\begingroup$

If none of numbers: $a,a+d,a+2d,...,a+(n-1)d$ are divisible by $n$,then prove that $n,d$ are coprime.

Since none of the given numbers are divisible by $n$,then their remainders mod $n$ are $1,2,...,n-1$.Based on pigeon hole principle I deduce that there are two numbers among them such that:
$$a+(i-1)d\equiv a+(j-1)d\pmod n,(0<i,j<n)\Rightarrow$$ $$(i-j)d\equiv 0\pmod n$$
Which means $n|d$ because $i-j<n$.What's wrong with my solution which contradicts the problem??!!

$\endgroup$
  • 1
    $\begingroup$ $2\cdot 3 \equiv 0 \pmod{6} $ and since $2 <6$ by your logic we conclude $6|3$. See the problem? $\endgroup$ – Sil Dec 3 '17 at 8:30
  • $\begingroup$ @Sil I found my mistake,but what's the correct solution? $\endgroup$ – Hamid Reza Ebrahimi Dec 3 '17 at 8:32
  • 1
    $\begingroup$ Correct conclusion is that there is a prime $p $ such that $p|n $ and $p|d $, meaning that $(n,d) >1$. In other words they cannot be coprime. $\endgroup$ – Sil Dec 3 '17 at 8:40
  • $\begingroup$ I'm not sure the problem statement is wrong, as it's been asked sometime ago independently... $\endgroup$ – Hamid Reza Ebrahimi Dec 3 '17 at 8:41
  • $\begingroup$ It is wrong, and the other question has it wrong as well. If you look closely at the answer provided there, it shows that assuming they are coprime leads to contradiction, so again, they cannot be coprime. $\endgroup$ – Sil Dec 3 '17 at 8:44
4
$\begingroup$

The problem statement is incorrect. The conclusion should instead be that $n$ and $d$ are not coprime.

Your argument is not quite right, though. You know $(i-j)d$ is divisible by $n$, but this does not mean $n$ divides $d$ since $n$ may not be prime.

$\endgroup$
1
$\begingroup$

A quick counter-example $1, 1+1\cdot2, 1+2\cdot2, 1+3\cdot2=1+(4-1)\cdot2$ none divisible by $4$, but $\gcd(4,2)=2$.

Getting to the conclusion that $(i-j)d\equiv 0\pmod n$ (which is $(i-j)d=n\cdot Q_1$) is good, but not enough as it was pointed already. Let's assume that $\gcd(d,n)=1$, this means that $d$ and $n$ has no common factors. So every $p$-prime factor of $n$ will divide $i-j$ (otherwise $\gcd(d,n)\geq p >1$), concluding that $n \mid (i-j) < n$ which is a contradiction for $\gcd(d,n)=1$. So $\gcd(d,n)\ne1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.