Results 1 to 3 of 3

Math Help - [SOLVED] Proof of divisibility

  1. #1
    Newbie
    Joined
    Oct 2007
    Posts
    6

    Exclamation [SOLVED] Proof of divisibility

    Hi,
    I am having difficulty with some proofs.

    Show that every composite integer of the form 4n+3 has a factor of the form 4m+3.

    and

    Show that every composite integer of the form 6n+5 has a factor of the form 6m+5.
    Last edited by R.Laramee; October 25th 2007 at 08:44 PM. Reason: change description
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by R.Laramee View Post
    Hi,
    I am having difficulty with some proofs.

    Show that every composite integer of the form 4n+3 has a factor of the form 4m+3.
    I do this one.

    Note the number is not even, so its prime factors are all odd. Hence they have the form 4k+1\mbox{ or }4k+3. Note that if all prime factors had the form 4k+1 then their overall product also have the same form. Which is impossible because the number has the form 4k+3. This means at least of these prime factors must have the form 4k+3.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by R.Laramee View Post
    Hi,
    I am having difficulty with some proofs.

    Show that every composite integer of the form 4n+3 has a factor of the form 4m+3.

    and

    Show that every composite integer of the form 6n+5 has a factor of the form 6m+5.
    Suppose x is composite and of the form 4n+3, and let a and b be such that
    ab=x. Then a is of the form 4m, 4m+1 or 4m+2 for some m, and b is of the
    form 4k, 4k+1, or 4k+2. But then ab is not of the form 4n+3, a contradiction.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 13th 2010, 11:05 AM
  2. Divisibility Proof
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: February 19th 2010, 01:01 AM
  3. [SOLVED] On Divisibility by 19
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 14th 2009, 08:23 AM
  4. Replies: 2
    Last Post: July 8th 2008, 01:05 PM
  5. [SOLVED] Proof of divisibility by Induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 14th 2007, 08:15 PM

Search Tags


/mathhelpforum @mathhelpforum