Show that if each number {b, a + b, 2a + b, ...., (n-1)a + b} is prime then every prime p <= n, must divide a, i.e. p | a
Note that if we had $\displaystyle \{b,\,a+b,\,\ldots,\,(n-1)a+b\}=\{0,\,1,\,2,\ldots,\,n-1\}\!\!\!\pmod n$ , then if $\displaystyle q$ is any prime dividing $\displaystyle n$ we'd have that
$\displaystyle q=(ka+b)\!\!\!\pmod n\iff q=(ka+b)+xn\,,\,\,for\,\,\,some\,\,\,k,\,x\in\math bb{Z}\,,\,\,0\leq k<n-1$ .
But $\displaystyle q\mid xn\,,\,q\mid q\Longrightarrow q\mid (ka+b)$ , and this is impossible since $\displaystyle ka+b$ is a prime $\displaystyle \forall k=0,1,\ldots,n-1$ $\displaystyle \Longrightarrow \{b,\,a+b,\,\ldots,\,(n-1)a+b\}\neq\{0,\,1,\,2,\ldots,\,n-1\}\!\!\!\pmod n$
and since there are $\displaystyle n$ different numbers in $\displaystyle \{b,\,a+b,\ldots,\,(n-1)a+b\}$ then there must exist $\displaystyle 0\leq k,j<n-1\,,\,\,k\neq j$ , s.t.
$\displaystyle ka+b=ja+b\!\!\!\pmod n\Longrightarrow (k-j)a=0\!\!\!\pmod n\Longrightarrow$ any prime dividing $\displaystyle n$ also divides $\displaystyle a$ (hmmm...why?? Just a little explanation more...).
Tonio
$\displaystyle b, a+b , 2a + b , ... , (n-1)a + b $
We have $\displaystyle (k,b) = 1 $ for $\displaystyle k=2,3,...,n-1$ otherwise , that term would not be a prime .
Also $\displaystyle b \neq 1 $ because $\displaystyle 1 $ is not a prime .
Therefore , $\displaystyle b > n-1 $
Let's consider the lemma ,
$\displaystyle b(a+b)(2a+b)...((n-1)a+b) $ is divisible by $\displaystyle n!$ provided that $\displaystyle a $ is prime to $\displaystyle n! $
Proof :
Take modulo $\displaystyle n!$ and since $\displaystyle a $ is prime to it , there is an inverse of it , let $\displaystyle a^{-1} = t$
$\displaystyle b(a+b)(2a+b)...((n-1)a+b) \equiv a^n (bt)(bt+1)(bt+2)...(bt+ n-1) \bmod{n!} \equiv 0 \bmod{n!} $ , it is deduced by using the fact that $\displaystyle \binom{n}{k}$ is an integer .
Consider
$\displaystyle b(a+b)(2a+b)...(a(k-1)+b) $
It should be divisible by $\displaystyle k! $ if $\displaystyle a $ is prime to $\displaystyle k! , k = 2,3,...,n-1 $ but we have each term is prime $\displaystyle \geq b > n-1 \geq k$ , we have the product $\displaystyle b(a+b)(2a+b)...(a(k-1)+b) $ contains prime factors that all are greater than $\displaystyle k $ , which is prime to $\displaystyle k , k-1 , k-2 ,..., 2$ . Therefore , $\displaystyle a $ is prime to $\displaystyle k !$ is false for $\displaystyle k =2 , 3, ..., n-1 $ and we have that$\displaystyle a $ contains all prime $\displaystyle <n$ .
Consider $\displaystyle 5,11,17,23,29 $ , $\displaystyle n=5 , a = 6 , b=5$ ,
$\displaystyle a = 6 $ contains $\displaystyle 2,3$ these two prime numbers but not also $\displaystyle 5 $ . It is not true that every prime $\displaystyle p \leq n$, must divide a , it should be $\displaystyle p <n$
I find that i can simplify the solution i gave ... Maybe the first thing is to modify the lemma i introduced ...
Lemma:
$\displaystyle b(a+b)(2a+b)...((n-1)a+b)$ is divisible by $\displaystyle x $ where $\displaystyle x | n! $ provided that $\displaystyle a $ is prime to $\displaystyle x $ .
The proof is quite similar to that of the original lemma .
Then , we just need to consider the product :
$\displaystyle b(a+b)(2a+b)...(({\color{red}{n-2}})a+b)$
Let $\displaystyle x $ be the prime not exceeding $\displaystyle n-1$ ie $\displaystyle x = p < n $ .
It is divisible by $\displaystyle p $ if $\displaystyle a $ is prime to $\displaystyle p $ . However , each of the terms is prime $\displaystyle \geq b > n-1 $ so it doesn't contain the prime $\displaystyle p $ , a contradiction makes us to say ' $\displaystyle a $ is prime to $\displaystyle p$' is false and $\displaystyle (a,p) \neq 1 \implies p|a $ .
Note: We can also say $\displaystyle p|a$ for $\displaystyle p \leq n $ if $\displaystyle b \neq n $ . In the counterexample I gave , it is coincident that $\displaystyle n = b = 5$ . Not being in this case , the statement is true .