Bizonyítsuk be, hogy ha n páratlan, akkor n = 4k + 1 néhány k esetében ZZ-ben, vagy n = 4k + 3 néhány k esetében ZZ-ben?

Íme egy alapvető vázlat:

Javaslat: Ha # N # akkor furcsa # N = 4k + 1 # néhány #k a ZZ-ben vagy # N = 4k + 3 # néhány #k a ZZ-ben.

Bizonyíték: Legyen #n a ZZ-ben hol # N # furcsa. Feloszt # N # 4-el.

Ezután megosztási algoritmus szerint # R = 0,1,2, # vagy #3# (maradék).

1. eset: R = 0. Ha a maradék #0#, azután # N = 4k = 2 (2k) #.

#:. n # egyenlő

2. eset: R = 1. Ha a maradék #1#, azután # N = 4k + 1 #.

#:. n # furcsa.

3. eset: R = 2. Ha a maradék #2#, azután # N = 4k + 2 = 2 (2k + 1) #.

#:. n # egyenlő.

4. eset: R = 3. Ha a maradék #3#, azután # N = 4k + 3 #.

#:. n # furcsa.

#:. n = 4k + 1 vagy n = 4k + 3 # ha # N # furcsa