Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: How does one know to begin this proof by [...]? (Modulo proof by cases)

  1. #1
    s3a
    s3a is offline
    Super Member
    Joined
    Nov 2008
    Posts
    621

    How does one know to begin this proof by [...]? (Modulo proof by cases)

    For the proof of #9 (which is a proof by cases - https://en.wikipedia.org/wiki/Proof_by_exhaustion), here ( https://www.docdroid.net/nAduS30/9.pdf ), how does one know to begin the proof by evaluating each case of the modulo expression p mod 6?

    I feel like it's related to the 6 in p^2 = 6k + 1, but I don't really understand the specifics, assuming that that is even the reason.

    Could someone please elaborate on that for me?

    Any input would be GREATLY appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,634
    Thanks
    1458

    Re: How does one know to begin this proof by [...]? (Modulo proof by cases)

    This is based on the Division Theorem:

    Division Theorem

    This is the basis for the definition of modular arithmetic. So, saying $p^2=6k+1$ is equivalent of saying that $p^2 \equiv 1 \pmod{6}$. Each statement implies the other.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    s3a
    s3a is offline
    Super Member
    Joined
    Nov 2008
    Posts
    621

    Re: How does one know to begin this proof by [...]? (Modulo proof by cases)

    Thanks for the response.

    But, how does having to prove that p^2 ≡ 1 (mod 6) mean that I have to start the proof by evaluating the expression p (not squared) ≡ r_i (mod 6), for each case, where i = 0, 1, 2, 3, 4, or 5, depending on the case (since d = 6, and it must be the case that both i >= 0 and i < d = 6)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,926
    Thanks
    3098

    Re: How does one know to begin this proof by [...]? (Modulo proof by cases)

    It doesn't! That is not the only way to solve "p^2= 1 (mod 6)" but since it only involves squaring 6 numbers, it is by far the easiest way. If the problem were to find p such that "p^2= 1 (mod 3487392)" that might not be the case.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    s3a
    s3a is offline
    Super Member
    Joined
    Nov 2008
    Posts
    621

    Re: How does one know to begin this proof by [...]? (Modulo proof by cases)

    Sorry, HallsofIvy; I didn't express my question correctly.

    I meant:
    Prior to performing the proof, why would one suspect that evaluating (each case of) the expression p (not squared) ≡ r_i (mod 6) would yield the desired result?

    (Hopefully thatís clearer.)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,634
    Thanks
    1458

    Re: How does one know to begin this proof by [...]? (Modulo proof by cases)

    Quote Originally Posted by s3a View Post
    Sorry, HallsofIvy; I didn't express my question correctly.

    I meant:
    Prior to performing the proof, why would one suspect that evaluating (each case of) the expression p (not squared) ≡ r_i (mod 6) would yield the desired result?

    (Hopefully that’s clearer.)
    Experience. Over time, mathematicians spot patterns when writing proofs. Common thought processes that lead to the results they seek. Many of these thought processes are difficult to articulate. I think that is what makes it difficult for me to answer your question. I look at the problem and it screams at me to consider $p \pmod 6$. But I am not sure what to say to you so that you would immediately think that, too.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by cases example
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 29th 2014, 02:30 PM
  2. Replies: 2
    Last Post: Nov 18th 2011, 09:49 PM
  3. Proof by Cases
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 18th 2009, 09:36 AM
  4. Proof by cases
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 15th 2007, 02:06 AM
  5. Is this a proof by cases?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 9th 2007, 05:24 AM

/mathhelpforum @mathhelpforum