Question

Aratati ca daca a =b(mod n), atunci (a, n) = (b,n), unde a,b,n sunt numere naturale.

Answer 1

Proprietăți:

(a, b) = (b, a mod b)

(a mod b) mod b = a mod b

Rezolvare:

a = b mod n

(a, n) = (n, a mod n)

=  (n, (b mod n) mod n))

= (n, b mod n)

= (b, n)