Udowodnij,że liczby są względnie pierwsze.

[Vent]

Bardzo proszę o pomoc, podpowiedzi związane z zadaniami :

1. Liczbą Euklidesa nazywamy liczbę ek zdefiniowaną przez indukcję następująco : \(\displaystyle{ e_{1} = 1, e_{k+1} = e_{1}*e_{2}*...*e_{k} + 1.}\) Udowodnij, że dowolne dwie liczby Euklidesa są względnie pierwsze.


2. W pewnym bankomacie są tylko monety o wartościach a zł i b zł. Wiadomo, że \(\displaystyle{ NWD (a,b) = 1}\), oraz że bankomat wyda dowolną kwotę większą od pewnej liczby \(\displaystyle{ n _{0}}\) (zależnej od konkretnych wartości a i b).
Zaprojektuj algorytm, który wylicza liczbę monet każdego z typów przy realizacji kwoty \(\displaystyle{ n}\) zł, o ile \(\displaystyle{ n>n _{0} .}\) Wyznacz wartość \(\displaystyle{ n _{0}}\) w Twoim algorytmie.
Algorytm powinien działać z kosztem czasowym stałym. Wśród dozwolonych operacji mogą wystąpić operacje div i mod.
Poprawność działania algorytmu musi być poparta odpowiednimi rozważaniami matematycznymi.

[porfirion]

Cóż, chyba nie poświęciłeś zbyt dużo czasu starając się rozwiązać zadanie pierwsze...
Co do drugiego, to przy niezerowej wiedzy z teorii liczb, też nie jest trudne - szczególnie, że masz zaproponować coś co działa (a niekoniecznie coś co działa najlepiej). Sam bym użył do tego tw. Eulera (co dość miażdży problem (jak mamy 1 mod coś tam to mamy już dowolną resztę mod to coś tam)). Ale jeśli chcesz wiedzieć jakie \(\displaystyle{ n_{0}}\) jest optymalne, to spójrz tu: ... et_Theorem