Results 1 to 6 of 6

Math Help - 2 Prime Number questions

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    27

    2 Prime Number questions

    1.
    Let n be an integer greater than 0. Show that there is a prime p such that p | n (p divides n). Don't use the theorem that every integer greater than 1 can be expressed as a product of prime numbers.
    I really don't know how to go about solving this one without using the theorem I can't use

    2.
    Let p be prime, p >= 5. Show that p is of the form 6k+1 or 6k+5 for some integer k.
    I was trying to use induction here but get stuck trying to prove for n+1 (I was inducting over k)

    Thanks for any help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    1) n has to be greater than 1 !

    If n is prime we are done, so let's assume that n is not prime. Then n=a_1\cdot{b_1} for some a_1,b_1\geq{2}. If a_1 is prime, we are done. If this is not so, then a_1=a_2\cdot b_2 for some a_2,b_2\geq{2} that is n=a_2\cdot b_2 \cdot b_1 \geq{2^3}

    Now repeat this process. We can ensure it will end since after m steps we get n=a_m\cdot b_m\cdot b_{m-1}\cdot ..\cdot b_1\geq{2^{m+1}} and this doesn't hold for large enough m.

    This proves that at some point a_{m} is going to be prime. (since this ends if and only if a_m is prime) .And we are done.

    2). Simple note that 6k+2 is even, ( so if k>0 then it is a number greater than 2 and divisible by it, hence not prime). 6k+3=3(2k+1) is multiple of 3, so it only can be prime if it is 3 itself. 6k+4=2(3k+2) (again even) ...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Maybe you'll find this proof of 1) clearer than the other one.

    If n>1 then the set <br />
A = \left\{ {d \in \mathbb{Z}^ +  ,d > 1/\left. d \right|n} \right\}<br />
is non-empty ( since n\in A ) further <br />
A \subset \mathbb{N}<br />
thus <br />
k = \min \left( A \right)<br />
exists.

    If k was not prime then <br />
k = a \cdot b<br />
with a,b>1, but then a|n ( n=k\cdot u = a\cdot (b\cdot u)) and so <br />
a \in A \wedge a < \min \left( A \right) = k<br />
contradiction ! Thus k is prime and we are done.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    Quote Originally Posted by PaulRS View Post
    1) n has to be greater than 1 !

    If n is prime we are done, so let's assume that n is not prime. Then n=a_1\cdot{b_1} for some a_1,b_1\geq{2}. If a_1 is prime, we are done. If this is not so, then a_1=a_2\cdot b_2 for some a_2,b_2\geq{2} that is n=a_2\cdot b_2 \cdot b_1 \geq{2^3}

    Now repeat this process. We can ensure it will end since after m steps we get n=a_m\cdot b_m\cdot b_{m-1}\cdot ..\cdot b_1\geq{2^{m+1}} and this doesn't hold for large enough m.

    This proves that at some point a_{m} is going to be prime. (since this ends if and only if a_m is prime) .And we are done.

    2). Simple note that 6k+2 is even, ( so if k>0 then it is a number greater than 2 and divisible by it, hence not prime). 6k+3=3(2k+1) is multiple of 3, so it only can be prime if it is 3 itself. 6k+4=2(3k+2) (again even) ...
    First of all thanks,
    I do have some questions though, just better insight for me

    1)
    Do we have to worry about what that first b1 is? Or is it okay to just leave it an integer (which I'm guessing after it all happens is just 1?)

    2)
    Are you just showing that since it holds for 6k+1
    Doesn't hold for 6k+2, since 2(3k+1) is a multiple of 2
    Doesn't hold for 6k+3, since 3(2k+1) so multiple of 3 unless k = 0
    Doesn't hold for 6k+4, since 2(3k+2), multple of 2
    Hold's for 6k+5

    Do you just have to cover the interval of 1-5? I just can't see how this proves that p is of the forms for any p >= 5.

    It seems like it can hold for 6k+7 too? or 6k + any prime.

    Thanks again for your time
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943
    6k+7 = 6k+6+1 = 6(k+1)+1. Letting k+1=j, we have 6j+1, which is exactly what we've already stated is true.

    The statement is really: Any prime can be expressed as 6k+a, where a\,mod\,6\equiv1 or a\,mod\,6\equiv5.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by Th3sandm4n View Post
    1)
    Do we have to worry about what that first b1 is? Or is it okay to just leave it an integer (which I'm guessing after it all happens is just 1?)
    The idea is that b_1 and the rest of the b's ( if they appear) are integers greater than 1, read the proof again. We do not care what they are because it is enough to just work with the a's in order to get a prime number, we could also decompose each of the b's in the same way, and we'd get that n can be written as a product of prime numbers.

    Also read the second proof ( my second post)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 24th 2011, 11:23 AM
  2. Replies: 1
    Last Post: September 2nd 2009, 08:31 AM
  3. Some Prime Number Divisibility Questions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 08:17 PM
  4. prime number questions
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 22nd 2008, 09:09 AM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum