Zadania z Teorii liczb - NWD

1. Niech a

1

, a

2

, ..., a

n

∈ Z i przynajmniej jedna z tych liczb jest ró»na od 0. Liczba naturalna d jest

równa NW D(a

1

, a

2

, ..., a

n

)

wtedy i tylko wtedy, gdy

(a) ∀ i = 1, 2, ..., n

d|a

i

(b) je±li istnieje taka liczba b ∈ Z, »e b|a

i

dla ka»dego i = 1, 2, ..., n, to b|d.

2. Niech n ∈ Z. Jakie s¡ mo»liwe warto±ci NW D(n, n + 2) oraz NW D(n, n + 6)?

3. Znale¹¢ najmniejsz¡ liczb¦ naturaln¡ w podanym zbiorze:

(a) {6u + 15v, u, v ∈ Z} {12r + 17s, r, s ∈ Z}.

4. Niech a, b, u, v ∈ Z. Pokaza¢, »e je±li au + bv = d > 1 to NW D(a, b) nie musi by¢ równe d.

5. Udowodni¢, »e

(a) NW D(a, b) | NW D(a + b, a − b)

(b) je±li jedna z liczb jest nieparzysta, a druga parzysta, to NW D(a, b) = NW D(a + b, a − b)

(c) je±li obie liczby s¡ nieparzyste, to 2NW D(a, b) = NW D(a + b, a − b).

6. Pokaza¢, »e prawdziwe s¡ nast¦puj¡ce wzory:

(a) ∀ a, b, c ∈ Z, a 6= 0

a|bc ∧

N W D(a, b) = 1 =⇒ a|c

(b) ∀ a, b, r, q ∈ Z, b 6= 0

a = bq + r =⇒ N W D(a, b) = N W D(b, r)

(c) ∀ a, b ∈ Z, a

2

+ b

2

> 0

∃ u, v ∈ Z

N W D(a, b) = au + bv

(d) ∀ a, b, d ∈ Z, a

2

+ b

2

> 0

N W D(a, b) = d =⇒ N W D

a
d

,

b

d

= 1

(e) ∀ a, b, c ∈ Z, a

2

+ b

2

> 0, c > 0

N W D(ac, bc) = cN W D(a, b)

(f) ∀ a, b, c ∈ Z, a 6= 0, b 6= 0

a|c ∧

b|c ∧ N W D(a, b) = 1 =⇒ ab|c

(g) ∀ a, b, c ∈ Z, a 6= 0

a|bc ∧ N W D(a, b) = 1 =⇒ a|c

(h) ∀ n ∈ Z

N W D(n, n + 1) = 1

(i) ∀ n ∈ Z

N W D(n + 1, n

2

− n + 1) ∈ {1, 3}.

(j) ∀ a, b ∈ Z, a

2

+ b

2

> 0

N W D(N W D(a, b), b) = N W D(a, b)

(k) ∀ a, b, c ∈ Z, a 6= 0

a|b + c ∧ N W D(b, c) = 1 =⇒ N W D(a, b) = 1 = N W D(a, c).

(l) ∀ a, b ∈ Z

N W D(a, 4) = 2 ∧ N W D(b, 4) = 2 =⇒ N W D(a + b, 4) = 4.

(m) ∀ a, b, d ∈ Z, a

2

+ b

2

> 0

N W D(a, a + b) = d ⇐⇒ N W D(a, b) = d.

(n) ∀ a, b, t ∈ Z

N W D(a, b) = N W D(a, b + at)

(o) ∀ a, b, n ∈ Z, a

2

+ b

2

> 0, n > 0

N W D(a, b) = 1 =⇒ N W D(a, b

n

) = 1

(p) ∀ a, b, c, d ∈ Z, c 6= 0

c|ab ∧ N W D(a, c) = d =⇒ c|bd.

(q) ∀ a, b ∈ Z, a

2

+ b

2

> 0

N W D(a, b, c) = N W D(N W D(a, b), c) = N W D(a, N W D(b, c))

(r) ∀ a, b ∈ Z, a

2

+ b

2

> 0

N W D(5a + 4b, 4a + 3b) = 1 ⇐⇒ N W D(a, b) = 1

(s) ∀ a, b, c ∈ Z, a

2

+ c

2

> 0, b

2

+ c

2

> 0

N W D(a, c) = N W D(b, c) = 1 =⇒ N W D(ab, c) = 1.

(t) ∀ a, b, d ∈ Z, a

2

+ b

2

> 0

N W D(a, b) = d =⇒ ∃ r, s ∈ Z

a = rd ∧ b = sd ∧ N W D(r, s) = 1

(u) ∀ a, b ∈ Z, a

2

+ b

2

> 0

N W D(a, b) = N W D(−a, b) = N W D(a, −b) =

= N W D(−a, −b) = N W D(b, a) = N W D(|a|, |b|)