Finden Sie ganze Zahlen x,y, so dass gilt: x*161 + y*126 = ggT(161,126)

Question

Finden Sie ganze Zahlen x,y, so dass die folgende Gleichung gilt:

$$x \cdot 161 + y \cdot 126 = \operatorname { gg } \mathrm { T } ( 161,126 )$$

Comments

 

Ich bestimme erst mal den ggT

161 : 126 = 1 Rest 35

126 : 35 = 3 Rest 21

35 : 21 = 1 Rest 14

21 : 14 = 1 Rest 7

14 : 7 = 2 Rest 0

ggt = 7

Zu lösen ist nun noch:  161x + 126y - 7 = 0 in Z

Also 7(23x + 18y) = 7

D.h. 23 x + 18y = 1 resp. 18y = 1 - 23x

y=(1-23m)/18

x=(1-18n)/23

Komme da nicht direkt weiter. Deshalb schaue ich mal bei WolframAlpha, was da rauskommen könnte.

z.B. x=11 und y = -14

oder x= -7 und y = 9

Dass 18 und 23 die Perioden von x und y sein müssen mit unterschiedlichem Vorzeichen. Liess sich an 18y = 1 - 23x ablesen. 

Jetzt müsste man nur noch  die 11 und die - 14 irgendwie berechnen können…

Vielleicht findest du da selbst noch einen Trick.

7 = 21-14

14 = 35 - 21

21 = 126 - 3*35

35 = 161 - 126

Answer 1

Teilermengen von

161 ={ 1,7,23,161}

126={1,2,3,6,7,14,18,21,42,63}

 der ggT =7

x*161 +y*126=7

7(23x+18y)=7     | 7

   23x+18y=1

 

x=18n+11

y=-23n-14

n=1   (29| 37)

Answer 2

Wende den erweiterten euklidischen Algorithmus an.

(1)  161:126 = 1  Rest  35
       ⇔  35 = 161 - 1·126

(2)  126:35 = 3  Rest  21 
       ⇔  21 = 126 - 3·35 = 126 - 3·(161 - 1·126) = 4·126 - 3·161

(3)  35:21 = 1  Rest  14
       ⇔  14 = 1·35 - 21 = 1·(161 - 1·126) - (4·126 - 3·161) = 4·161 - 5·126

(4)  21:14 = 1  Rest  7
       ⇔  7 = 21 - 1·14 = (4·126 - 3·161) - 1·(4·161 - 5·126) = 9·126 - 7·161

(5)  14:7 = 2  Rest  0.

Damit ist ggT(161,126) = 7 = 9·126 - 7·161.