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

Printable View

- May 17th 2010, 11:59 PMSmithPrime numbers.
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

- May 18th 2010, 04:54 AMtonio

Note that$\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__if we had__

$\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...(Giggle)).

Tonio - May 18th 2010, 06:59 AMsimplependulum
$\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$ - May 18th 2010, 07:09 AMwonderboy1953Thought
These would be excellent questions for the math challenge section.

- May 18th 2010, 08:38 PMsimplependulum
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 .