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

1. 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!

2. 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.

3. 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)?

4. 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.

5. 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.)

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

Originally Posted by s3a
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.