Results 1 to 12 of 12

Math Help - Formal Modulus Proof: How close am I?

  1. #1
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    Formal Modulus Proof: How close am I?

    Show that if n is an odd positive integer then n^2 = 1(mod 8).

    I see that any odd square has 1 as a remainder when calculated. Example: 49 = 7 * 7 = 1(mod 4), and any odd number squared equals an odd number. Let 2k represent all positive even integers. So n^2 = 1(mod 2k) for all odd positive integers.

    Is this an acceptable proof?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by aaronrj View Post
    Show that if n is an odd positive integer then n^2 = 1(mod 8).

    I see that any odd square has 1 as a remainder when calculated. Example: 49 = 7 * 7 = 1(mod 4), and any odd number squared equals an odd number. Let 2k represent all positive even integers. So n^2 = 1(mod 2k) for all odd positive integers.

    Is this an acceptable proof?
    no, this proof is not acceptable. especially since you are trying to prove it with examples.

    Assume n is odd. then we can write n = 2k + 1 for some integer k.

    but that means n^2 = (2k + 1)^2 = 4k^2 + 4k + 1

    now all you need to show is that you can write that expression in the form 8m + 1 for some integer m. since all numbers equivalent to 1 mod 8 have that form
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    need more help

    Sorry, I see where you're going but I can't fill in the steps.

    We have 4k^2 + 4k + 1

    How does 8m + 1 fit into that?

    Sub in 8m+1 for k?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by aaronrj View Post
    Sorry, I see where you're going but I can't fill in the steps.

    We have 4k^2 + 4k + 1

    How does 8m + 1 fit into that?

    Sub in 8m+1 for k?
    no, here's a further hint: leave the +1 alone and factor an 8k out of the first two terms. you get

    8k(k + 1)/2 + 1

    now, obviously, your task is to find out whether k(k + 1)/2 is an integer
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    Correct Proof

    Take 4k^2 + 4k + 1 = n^2
    Factor: 4(k^2 + k) + 1 - 1 = n^2 - 1
    Therefore: 4(k^2 + k) = n^2 - 1

    This is how the book proves it.

    I don't see where you were going with:

    8k(k + 1)/2 + 1

    Perhaps a bit more clarity is needed next time you attempt to offer aid.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by aaronrj View Post
    Take 4k^2 + 4k + 1 = n^2
    Factor: 4(k^2 + k) + 1 - 1 = n^2 - 1
    Therefore: 4(k^2 + k) = n^2 - 1

    This is how the book proves it.

    I don't see where you were going with:

    8k(k + 1)/2 + 1

    Perhaps a bit more clarity is needed next time you attempt to offer aid.
    that proof is not correct. look up the definition for a \equiv b \mod n. you will see that it means n \mid (a - b) \Longleftrightarrow a - b = nk for some k \in \mathbb{Z}.

    thus, saying 4(k^2 + k) = n^2 - 1 is saying n^2 \equiv 1\mod {\color{red}4} not \mod 8

    to show that n^2 \equiv 1\mod 8 you must show that 8 \mid (n^2 - 1), or in other words, n^2 - 1 = 8k for some integer k. that is what i was telling you to do. we need 8m = n^2 - 1 for some integer m, provided n is odd.

    we got to the point n^2 - 1 = 8 \frac {k(k + 1)}2

    now, we complete the proof if we can show \frac {k(k + 1)}2 is an integer. that is what i leave it to you to do
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    Thanks.

    Well, I guess I need to double check all of the proofs given in the book. Perhaps the author got lazy when writing the solutions. Thanks for clarifying the proof.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by aaronrj View Post
    Well, I guess I need to double check all of the proofs given in the book. Perhaps the author got lazy when writing the solutions. Thanks for clarifying the proof.
    well, we're not done. how would you finish up? is that expression an integer or not?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    Did you not answer your own question?

    Doesn't the theorem explicitly state that the expression must be an integer?

    Theorem:
    Let m be a positive integer. The integers a and b are congruent modulo m if and only if there is an integer k such that a = b + km.

    I definately should have referred to the definition first before trying to solve the problem; I would have had a much easier time. Lesson learned.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by aaronrj View Post
    Doesn't the theorem explicitly state that the expression must be an integer?

    Theorem:
    Let m be a positive integer. The integers a and b are congruent modulo m if and only if there is an integer k such that a = b + km.

    I definately should have referred to the definition first before trying to solve the problem; I would have had a much easier time. Lesson learned.
    we are to prove that it is an integer. assuming it is is begging the question. of course, if they ask you to prove something, they already know it is true. you are required to show why.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    Predicate calculus

    Let p represent the statement "The integers a and b are congruent modulo m."

    Let q represent the statement "there is an integer k such that a = b + km."

    If p \Longleftrightarrow q

    The domain is the set of all integers Z.

    I don't think this is what you are looking for, but I thought I'd at least give it a shot.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by aaronrj View Post
    Let p represent the statement "The integers a and b are congruent modulo m."

    Let q represent the statement "there is an integer k such that a = b + km."

    If p \Longleftrightarrow q

    The domain is the set of all integers Z.

    I don't think this is what you are looking for, but I thought I'd at least give it a shot.
    aaronrj, pay attention. i left off exactly where you should pick up. i did everything for you except the last step. all i want you to tell me, is whether k(k + 1)/2 is an integer or not (and why). that is all. do that and you are done. stop beating around the bush. i told you these definitions already, what point is there bringing them up?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. formal proof of set
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 6th 2010, 10:36 PM
  2. Is My Answer Close to Right? Cyclic Group Proof
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: December 10th 2009, 07:22 AM
  3. formal proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 2nd 2009, 09:17 AM
  4. simple proof help (I think I'm really close)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 26th 2009, 07:25 AM
  5. Formal Proof
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 12th 2008, 02:43 PM

Search Tags


/mathhelpforum @mathhelpforum