Patunayan na kung n ay kakaiba, pagkatapos n = 4k + 1 para sa ilang mga k sa ZZ o n = 4k + 3 para sa ilang k sa ZZ?

Narito ang pangunahing balangkas:

Proposisyon: Kung # n # ay kakaiba, kung gayon # n = 4k + 1 # para sa ilang #k sa ZZ # o # n = 4k + 3 # para sa ilang #k sa ZZ #.

Katunayan: Hayaan #n sa ZZ # kung saan # n # ay kakaiba. Hatiin # n # sa pamamagitan ng 4.

Pagkatapos, sa pamamagitan ng paghahati algorithm, # R = 0,1,2, # o #3# (natitira).

Kaso 1: R = 0. Kung ang natitira ay #0#, pagkatapos # n = 4k = 2 (2k) #.

#:. n # ay kahit na

Kaso 2: R = 1. Kung ang natitira ay #1#, pagkatapos # n = 4k + 1 #.

#:. n # ay kakaiba.

Kaso 3: R = 2. Kung ang natitira ay #2#, pagkatapos # n = 4k + 2 = 2 (2k + 1) #.

#:. n # ay kahit na.

Kaso 4: R = 3. Kung ang natitira ay #3#, pagkatapos # n = 4k + 3 #.

#:. n # ay kakaiba.

#:. n = 4k + 1 o n = 4k + 3 # kung # n # ay kakaiba