Liczby wzglednie pierwsze

antyspam · Post autor: **antyspam** » 17 mar 2013, o 22:39

Udowodnij, że:
\(\displaystyle{ 5n + 3}\) i \(\displaystyle{ 7n + 4}\) są względnie pierwsze dla dowolnego n.

Podejrzewam, że trzeba użyć twierdzenia Eulera, ale co mi to da? I co dalej?

smigol · Post autor: **smigol** » 17 mar 2013, o 22:53

Raczej algorytmu Euklidesa.

antyspam · Post autor: **antyspam** » 17 mar 2013, o 23:00

Mogłbyś trochę jaśniej?
Nie wiem jak mam wyliczyć w takim razie dla tych wartości. Gdybym miał konkretne liczby to bym wiedział..

smigol · Post autor: **smigol** » 17 mar 2013, o 23:05

Algorytm Euklidesa opiera się na tym, że \(\displaystyle{ NWD(a,b)}\) równe jest \(\displaystyle{ NWD(a-b,b)}\).
Czego nie rozumiesz?

antyspam · Post autor: **antyspam** » 17 mar 2013, o 23:12

Tego jak użyć tutaj algorytmu Euklidesa. No jak mam dane n, to jak mogę wyznaczyć jej dzielniki?

smigol · Post autor: **smigol** » 17 mar 2013, o 23:16

Jak wyznaczać dzielniki liczby \(\displaystyle{ n}\) jest pytaniem, na które odpowiedź nie jest łatwa (patrz np. poszukiwanie liczb pierwszych...). Musisz (a raczej możesz) po prostu użyć algorytmu Euklidesa, żeby pokazać, że dwie liczby z zadania dla dowolnego \(\displaystyle{ n}\) są względnie pierwsze.

antyspam · Post autor: **antyspam** » 17 mar 2013, o 23:44

\(\displaystyle{ \begin{tabular}{c|c}
7n+4 & 5n+3 \\
2n+1 & 5n+3 \\
2n+1 & 3n+2 \\
2n+1 & n+1 \\
n & n+1 \\
n & 1 \\
\end{tabular}}\)

Czy o to chodzi? i teraz po prawej stronie mamy jedynkę, więc niezależnie od \(\displaystyle{ n, NWD\left( 7n+4, 5n+3\right)}\) będzie równe 1, czyż nie?

Bardzo dziękuję za pomoc

smigol · Post autor: **smigol** » 18 mar 2013, o 07:14

Dokładnie o to chodzi.