Results 1 to 5 of 5

Thread: Prime numbers.

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    10

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by Smith View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    715
    $\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$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    769

    Thought

    These would be excellent questions for the math challenge section.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jan 2009
    Posts
    715
    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 .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Oct 22nd 2011, 12:37 PM
  2. Prime numbers
    Posted in the Algebra Forum
    Replies: 5
    Last Post: Dec 29th 2010, 04:54 AM
  3. Do they have a name for these prime numbers?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 11th 2009, 03:34 PM
  4. prime numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Sep 15th 2008, 09:47 PM
  5. prime numbers
    Posted in the Number Theory Forum
    Replies: 14
    Last Post: Dec 5th 2007, 04:53 AM

Search Tags


/mathhelpforum @mathhelpforum