Prime numbers.

May 2010
10
0
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
 
Oct 2009
4,261
1,836
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\mathbb{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
 

simplependulum

MHF Hall of Honor
Jan 2009
715
427
\(\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\)
 
Oct 2009
769
87
Thought

These would be excellent questions for the math challenge section.
 

simplependulum

MHF Hall of Honor
Jan 2009
715
427
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 .