Diskret matematik · 2024-10-25

Uppgift 4

Uppgift 4

Du ska avgöra om den Diofantiska ekvationen $\left(3^{300} - 5^{60} \right)x+7y=12$ har lösningar. Gör detta genom att först skriva ned villkoret på $a,b,c \in \setZ$ som måste gälla för att den Diofantiska ekvationen $ax+by = c$ ska ha lösningar, och därefter avgöra om $7$ delar $3^{300} - 5^{60}$.

Visa lösningDölj lösning

Den Diofantiska ekvationen $ax+by = c$ heltalslösningar precis då $\SGD(a,b) \mid c$.

Vi har att \[ 3^{300} - 5^{60} \equiv_7 (3^2)^{150} - (5^2)^{30} \equiv_7 2^{150} - 4^{30} \equiv_7 (2^3)^{50} - (4^3)^{10} \equiv_7 1^{50} - 1^{10} = 0. \] Alltså gäller $\SGD(3^{300} - 5^{60},7) = 7$, och eftersom $12$ ej är delbart med 7, så saknar ekvationen lösningar.