Visa likhet inom största gemensamma delare
Hej
Enligt uppgiften ska jag visa att sgd(5n + 3, 7n + 4) = 1 för alla positiva heltal n. Jag har försökt lösa den med induktionsprincipen enligt bilden nedan och undrar om jag kan göra så då det inte står något om uppgiften i facit.
Tips: du kunde prova med att bevisa genom motsägelsebevis (se https://www.matteboken.se/lektioner/mattespecialisering/logik/bevis-och-motsagelsebevis).
Du kan alltså börja med att anta motsatsen av det du ska bevisa, dvs att det finns minst ett värde av n, för vilken sgd(5n+3, 7n+4) 1, tex sgd(5n+3, 7n+4) = d (d > 1). Och du ska komma till en motsägelse.
Om sgd(5n+3, 7n+4) = d, betyder att 5n+3 = dq1 (1) och 7n+4 = d × q2 (2), där q1 >1 och q2 > 1.
Om du nu subtraherar (1) från (2), så får du att 2n+1 = d × (q2-q1) = d × q3
Tror du att du kan fortsätta härifrån? (Se också liknande bevis för två andra tal: https://www.pluggakuten.se/trad/relativt-prima-1/)
