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 mod6?

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!