Prime numbers.

**Smith** · May 17th 2010, 11:59 PM

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

**tonio** · May 18th 2010, 04:54 AM

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<n-1$ .

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<n-1\,,\,\,k\neq 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

**simplependulum** · May 18th 2010, 06:59 AM

$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 $<n$ .

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 <n$

**wonderboy1953** · May 18th 2010, 07:09 AM

These would be excellent questions for the math challenge section.

**simplependulum** · May 18th 2010, 08:38 PM

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 .

Thread: Prime numbers.

LinkBack

Thread Tools

Display

Prime numbers.

Thought

Similar Math Help Forum Discussions

Using the fact that a pair of numbers is relatively prime to prove that one is prime

Prime numbers

Do they have a name for these prime numbers?

prime numbers

prime numbers

Search Tags