Ezeket a számelméleti példákat hogy lehet bizonyítani?

"Ha A és B legnagyobb közös osztója 1, akkor ebből következik, hogy A+B és A*B legnagyobb közös osztója is 1. "

Tegyük fel, hogy ez nem igaz, hanem A+B és A·B legnagyobb közös osztója k.

Mivel k osztója A·B-nek, ezért k prímtényezői közül valamelyek A osztói, a maradékok pedig B osztói. Legyen mondjuk p egy ilyen prím (k = p·k'), az általánosság megsértése nélkül feltehetjük, hogy prímtényezője A-nak is: A = p·A'

Ekkor A+B = p·A' + B a feltételezés szerint osztható k-val, tehát p-vel is. Ekkor viszont B-nek is osztója kell legyen p, ami ellentmondás, mert A-nak és B-nek nincs közös osztója.

"Ha A+B és A*B legnagyobb közös osztója 10, akkor ebből következik, hogy A és B legnagyobb közös osztója 10."

A és B prímtényezői legyenek a₁, a₂, ... illetve b₁, b₂, ...

A·B-nek osztója 10. Két eset lehet:

a)

A = 10·A' , pl. a₁=2, a₂=5

A+B = 10·A' + B is osztható 10-zel, ami azt jelenti, hogy B is osztható 10-zel, pl. b₁=2 és b₂=5

A+B = 10(A'+B')

Tehát A-nak és B-nek a 10 közös osztója. Még be kell látni, hogy a 10 a legnagyobb.

Mivel 10 a legnagyobb közös osztója A+B és A·B-nek, ezért (A'+B')-nek és (A'·B)-nek nincs közös prímtényezője. Ha mondjuk az a₃ is közös osztó lenne, akkor B'-nek is osztója kell legyen a₃, de nem az. Ami azt jelenti, hogy a₁=a₂ és b₁=b₂ kivételével nincs azonos a és b prím. Ezért A és B-nek a legnagyobb közös osztója a 10.

b)

A = 2·A', de 5-tel nem osztható: A = 2·(5A''+n), 1≤n≤4

B = 5·B', de 2-vel nem osztható: B = 5·(2B''+1)

A+B = 10·A''+2n + 10·B''+5

= 10·(A''+B'') + 2n+5

Ennek oszthatónak kell lennie 10-zel, vagyis 2n+5 = 10k

Az viszont lehetetlen, mert 2n+5 páratlan.

Tehát ilyen b) eset nincs.

"A és B legnagyobb közös osztója egyenlő 3*A+B-nek és 5*A+2*B-nek a legnagyobb közös osztójával."

Legyen A és B legnagyobb közös osztója k.

A = k·A'

B = k·B'

A' és B'-nek nincs közös prímtényezője, relatív prímek.

3A+B = k·(3A'+B')

5A+2B = k·(5A'+2B')

Ezeknek k közös osztója, be kell még látni, hogy k a legnagyobb, vagyis 3A'+B' és 5A'+2B' relatív prímek.

Tegyük fel, hogy nem, vagyis létezik egy p prím, hogy p | 3A'+B' és p | 5A'+2B'

(Biztos tanultátok az x|y jelölést arra, hogy x osztja y-t, vagyis y-nak osztója x.)

Több eset is van:

a) p=2

2 | 5A'+2B', ami azt jelenti, hogy 2|A', tehát A' = 2·A''

2 | 3·2·A'' + B', ami csak akkor lehet, ha 2|B', de akkor A' és B' nem relatív prím, ellentmondás.

b) p=3

Hasonlóan megy ez is (csak először a 3A'+B'-t kell nézni), ebből is hasonlóan ellentmondás lesz.

c) p=5

Ebből is hasonlóan ellentmondás lesz.

d) p≥7 prím

Ha A' vagy B'-nek osztója lenne p, akkor a másiknak is osztója kellene legyen, ellentmondás lenne.

Vagyis egyiknek sem osztója.

A' = p·A'' + a, ahol 1 ≤ a ≤ p-1

B' = p·B'' + b, ahol 1 ≤ b ≤ p-1

3A' + B' = p·(3A''+B'') + 3a+b

vagyis p | 3a+b

5A' + 2B' = p·(5A''+2B'') + 5a+2b

vagyis p | 5a+2b

Az is igaz kell legyen, hogy p | 2·(3a+b)

Az is, amit úgy kapunk, hogy ebből kivonjuk az 5a+2b-t:

p | (6a+2b) - (5a+2b) = a

Ami viszont ellentmondás, hisz 0 < a < p