Ezt hogyan lehet bizonyítani?

Ha számok ugyanazzal a számmal oszthatóak, akkor összegük és különbségük is osztható lesz ugyanazzal a számmal. Ebből következik az is, hogy ha egész számmal szorozzuk őket, akkor az oszthatóság ugyanúgy megmarad.

Van, amikor szerencsénk van, és ránézésre látható, hogy milyen iránybe érdemes elindulni. Ebben az esetben is könnyen rájöhetünk arra, hogy ha az elsőből veszünk kettőt, a másodikból hármat, akkor összeadva őket a következőt kapjuk:

2*(a-3b) + 3*(5a+b) = ... = 17a-3b, ezzel a 17a megjelent, már a csak a b-t kellene jól beállÍtani.

Tehát 17a-3b biztosan osztható lesz 13-mal. Ha ehhez hozzáadunk 13b-t (ami szintén osztható 13-mal minden esetben), akkor 17a+10b eredményt kapjuk.

Ha az állítás igaz, és 17a+9b is igaz, akkor annak is igaznak kell lennie, hogy (-b) is osztható 13-mal. Így viszont b is osztható kell, hogy legyen 13-mal.

Ha b osztható 13-mal, akkor a kiinduló feltételekből a b-s tagok lehúzhatóak, így már csak azt kell bizonyítanunk, hogy

Ha 13|a és 13|5a, akkor 13|17a, ez pedig triviálisan igaz.

Tehát az állítás igaz.

(1) 13|5a+b miatt 13|10a+2b

(2) 13|5a+b és 13|a-3b

=> 13|(5a+b)-(a-3b)=4a+4b=4(a+b)

=> 13|a+b

(3) Az előbbieket felhasználva:

13|(10a+2b)+7(a+b)=17a+9b

Legyen u=a-3b, v=5a+b, x=17a+9b

Figyeljük meg, hogy

4x=-7u+15b A fenltétel szerint a jobb oldal osztható 13-mal, így a bal oldal is; s mivel 4 relatív prím 13-hoz, így szükségképp 13|x=17a+9b, és pont ezt kellett belátni.