1. ## Prime 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

2. Originally Posted by Smith
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

3. $\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$

4. ## Thought

These would be excellent questions for the math challenge section.

5. 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 .