REA in LDE

Question 1

Kako dobimo največji skupni delitelj?

Answer 1

Največji skupni delitelj GCD dobimo kot zadnji ne ničelni ostanek v razširjenem Evklidovem algoritmu (REA). Obenem gcd(m, n) zapišemo kot celoštevilsko linearno kombinacijo števil m in n

Question 2

Kdaj sta si števili tuji?

Answer 2

Števili a in b sta si tuji, če imata za največji skupni delitelj le število 1. Pišemo: gcd(a, b) = 1

Question 3

Kaj je diofantska enačba?

Answer 3

Diofantska enačba je enačba z dvema neznankama. Zapišemo jo v obliki ax + by = c, kjer so a, b in c elementi celih števil ter iščemo celoštevilsko rešitev x, y.

Question 4

Kaj je praštevilo?

Answer 4

Praštevilo je število, ki ima natanko dva pozitivna delitelja: število 1 in samega sebe.

Question 5

Kaj je linearna diofantska enacba z dvema neznankama? Kdaj je taka enačba
rešljiva?

Answer 5

a. LDE z dvema neznankama: a×x + b×y = c , kjer so znani a, b, c
b. LDE je rešljiva, ko gcd(a,b) deli c