Matematyka.pl

Niech
\(\displaystyle{ \begin{cases} a_0 = 6 \\ a_{n} = a_{n-1} + NWD(n, a_{n-1}) \end{cases}}\)
Udowodnić, że \(\displaystyle{ NWD(n, a_{n-1}) }\) jest liczbą pierwszą, bądź jest równe 1 (dla dowolnego \(\displaystyle{ n}\)).

\(\displaystyle{ a_1=6+NWD(1,6)=6+1=7}\)
\(\displaystyle{ a_2=7+NWD(2,7)=7+1=8}\)
Dobrze wyliczyłem?

Tak, dobrze. I jak na razie się zgadza:
\(\mathrm{NWD}(1, a_0) = \mathrm{NWD}(1, 6) = 1\)
\(\mathrm{NWD}(2, a_1) = \mathrm{NWD}(2, 7) = 1\)
\(\mathrm{NWD}(3, a_2) = \mathrm{NWD}(3, 8) = 1\)

Można zauważyć, że \(\displaystyle{ NWD(n,a_{n-1})}\) dzieli \(\displaystyle{ n}\) bez reszty .

Najlepiej sobie wypisać kolejne pary i zaobserwować pewne fakty

Będę zapisywał dla prostoty:

zamiast:

\(\displaystyle{ NWD(x,y)}\)

będę pisał

\(\displaystyle{ (x,y)}\)

Zaczynamy od:

\(\displaystyle{ (1,6)=1}\)

\(\displaystyle{ (2,7)=1}\)

\(\displaystyle{ (3,8)=1}\)

\(\displaystyle{ (4,9)=1}\)

\(\displaystyle{ (5,10)=5}\) ,,,, \(\displaystyle{ 1=6 \mod 5}\)

\(\displaystyle{ (6,15)=3}\)

\(\displaystyle{ (7,18)=1}\)

.....

\(\displaystyle{ (11,22)=11}\) ,,, \(\displaystyle{ 7=18 \mod 11}\)

\(\displaystyle{ (12,33)=3}\)

\(\displaystyle{ (13,36)=1}\)

........................................

,,,,,,, \(\displaystyle{ 13=36 \mod 23}\)

............................................................................

Można zaobserwować pewną prawidłowość a mianowicie po serii par, których NWD wynosi jeden następuje para lub kilka par których

NWD jest większe od jeden, a my mamy wykazać, że:

\(\displaystyle{ (x,y)=1 \vee p}\)

Można zauważyć, że jeżeli zaczyna się seria w której

\(\displaystyle{ (x_{1},y_{1})=1}\)

To pierwsza para dla której NWD będzie różny od jeden, łatwo zauważyć, że:

skoro:

\(\displaystyle{ (x,y)=1}\) - i niech będzie to pierwsza para z serii liczb względnie pierwszych to:

\(\displaystyle{ x=y \mod K}\)

gdzie dla pewnego \(\displaystyle{ x}\)

\(\displaystyle{ (x+s,y+s)=K}\)

I jest to najmniejsze takie \(\displaystyle{ s}\)

Jeżeli by K była liczbą złożoną to mielibyśmy

\(\displaystyle{ K=Rpq}\)

to:

wynika z tego, że:

\(\displaystyle{ x=y \mod p}\)

zawsze więc możemy dobrać jak najmniejszą liczbą pierwszą no więc nasz pierwszy wspólny dzielnik zawsze będzie liczbą pierwszą, cnd...

Więc jest to prawda gdy mamy serię liczb względnie pierwszych to ta seria może się zakończyć

\(\displaystyle{ (x,y)=p}\)

A teraz następna sprawa co z seriami gdzie zaczynamy od:

\(\displaystyle{ (a_{1},b_{1})=p}\)

mamy:

\(\displaystyle{ a_{1}=pa, b_{1}=pb}\)

\(\displaystyle{ (pa,pb)=p, (a,b)=1}\)

Z warunków zadania następna para to:

\(\displaystyle{ (pa+1,pb+p)=R}\)

Pytanie czy \(\displaystyle{ R}\) musi być liczbą pierwszą lub jeden czy nie?

ale można zauważyć, że:

\(\displaystyle{ (pa+1,pb+p)=(pa+1,b+1)}\)

Bo \(\displaystyle{ p}\) nie dzieli \(\displaystyle{ pa+1}\)

Jest też jak najbardziej:

\(\displaystyle{ (pa,b)=1}\)

A następna para po: \(\displaystyle{ (pa,b)}\)

to:

\(\displaystyle{ (pa+1,b+1)}\)

A jak wiemy z pierwszej części zadania:

że skoro:

\(\displaystyle{ (pa,b)=1}\)

to:

\(\displaystyle{ (pa+1,b+1)=1 \vee p}\)

cnd...