Page 21 - Numbertheory

@ @@@óáÕÜa@óïÝibÔ

:

[Division Algorithm]

ba

rq

. 0 ≤ r < a  b = qa + r

r a b (quotient) q

. (remainder)

n ( n = a2 ) n ()

.1 0 4

.r =1 r =0 a = 2q + r

n = a2 = 4k . n = a2 = 4q 2 + 4qr + r 2 = 4(q 2 + qr ) + r 2

. r2 =1 r2 = 0 r =1 r =0

. n = a2 = 4k +1

٨