Results 1 to 5 of 5

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

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    715
     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
    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:

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

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Prime numbers
    Posted in the Algebra Forum
    Replies: 5
    Last Post: December 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: November 11th 2009, 03:34 PM
  4. prime numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 15th 2008, 09:47 PM
  5. prime numbers
    Posted in the Number Theory Forum
    Replies: 14
    Last Post: December 5th 2007, 04:53 AM

Search Tags


/mathhelpforum @mathhelpforum