# Math Help - Prime numbers.

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 $\{b,\,a+b,\,\ldots,\,(n-1)a+b\}=\{0,\,1,\,2,\ldots,\,n-1\}\!\!\!\pmod n$ , then if $q$ is any prime dividing $n$ we'd have that

$q=(ka+b)\!\!\!\pmod n\iff q=(ka+b)+xn\,,\,\,for\,\,\,some\,\,\,k,\,x\in\math bb{Z}\,,\,\,0\leq k .

But $q\mid xn\,,\,q\mid q\Longrightarrow q\mid (ka+b)$ , and this is impossible since $ka+b$ is a prime $\forall k=0,1,\ldots,n-1$ $\Longrightarrow \{b,\,a+b,\,\ldots,\,(n-1)a+b\}\neq\{0,\,1,\,2,\ldots,\,n-1\}\!\!\!\pmod n$

and since there are $n$ different numbers in $\{b,\,a+b,\ldots,\,(n-1)a+b\}$ then there must exist $0\leq k,j , s.t.

$ka+b=ja+b\!\!\!\pmod n\Longrightarrow (k-j)a=0\!\!\!\pmod n\Longrightarrow$ any prime dividing $n$ also divides $a$ (hmmm...why?? Just a little explanation more...).

Tonio

3. $b, a+b , 2a + b , ... , (n-1)a + b$

We have $(k,b) = 1$ for $k=2,3,...,n-1$ otherwise , that term would not be a prime .

Also $b \neq 1$ because $1$ is not a prime .

Therefore , $b > n-1$

Let's consider the lemma ,

$b(a+b)(2a+b)...((n-1)a+b)$ is divisible by $n!$ provided that $a$ is prime to $n!$

Proof :

Take modulo $n!$ and since $a$ is prime to it , there is an inverse of it , let $a^{-1} = t$

$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 $\binom{n}{k}$ is an integer .

Consider

$b(a+b)(2a+b)...(a(k-1)+b)$

It should be divisible by $k!$ if $a$ is prime to $k! , k = 2,3,...,n-1$ but we have each term is prime $\geq b > n-1 \geq k$ , we have the product $b(a+b)(2a+b)...(a(k-1)+b)$ contains prime factors that all are greater than $k$ , which is prime to $k , k-1 , k-2 ,..., 2$ . Therefore , $a$ is prime to $k !$ is false for $k =2 , 3, ..., n-1$ and we have that $a$ contains all prime $ .

Consider $5,11,17,23,29$ , $n=5 , a = 6 , b=5$ ,

$a = 6$ contains $2,3$ these two prime numbers but not also $5$ . It is not true that every prime $p \leq n$, must divide a , it should be $p

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:

$b(a+b)(2a+b)...((n-1)a+b)$ is divisible by $x$ where $x | n!$ provided that $a$ is prime to $x$ .

The proof is quite similar to that of the original lemma .

Then , we just need to consider the product :

$b(a+b)(2a+b)...(({\color{red}{n-2}})a+b)$

Let $x$ be the prime not exceeding $n-1$ ie $x = p < n$ .

It is divisible by $p$ if $a$ is prime to $p$ . However , each of the terms is prime $\geq b > n-1$ so it doesn't contain the prime $p$ , a contradiction makes us to say ' $a$ is prime to $p$' is false and $(a,p) \neq 1 \implies p|a$ .

Note: We can also say $p|a$ for $p \leq n$ if $b \neq n$ . In the counterexample I gave , it is coincident that $n = b = 5$ . Not being in this case , the statement is true .