Własności NWD

[insanis]

Proszę chociaż o jakieś wskazówki do tych dowodów, bo nie wiem za bardzo jak się za to zabrać


1) \(\displaystyle{ NWD\left( m,n\right) = NWD\left( n,m mod n\right)}\) dla każdego \(\displaystyle{ m,n \in Z}\) i \(\displaystyle{ n \neq 0}\)
2) \(\displaystyle{ NWD\left( km,kn\right) = k \cdot NWD\left(m,n\right)}\)
3) \(\displaystyle{ NWD\left(m,n\right)=1 \Rightarrow NWD\left( mk,n\right) = NWD\left( k,n\right)}\)
4) \(\displaystyle{ NWD\left(m,k\right)=1 \wedge NWD\left( n,k\right) = 1 \Rightarrow NWD\left( mn,k\right) = 1}\)
5) \(\displaystyle{ NWD\left( k^{m}-1,k^{n}-1 \right)=k^{NWD\left( m,n\right)}-1}\) dla każdego \(\displaystyle{ m,n \in Z}\) i \(\displaystyle{ k \ge 2}\)
6) \(\displaystyle{ NWD\left(m,n\right)=1 \Rightarrow NWD\left( 2^{m}-1,2^{n}-1\right)=1}\)
7) Obliczyć \(\displaystyle{ NWD\left( 3^{288}-1,3^{216}-1\right)}\)

[Premislav]

7) \(\displaystyle{ gcd(288, 216)=72}\). Proponuję rozpisać \(\displaystyle{ 3^{288}-1}\) jako \(\displaystyle{ (3^{72})^{4}-1^{4}}\), zaś \(\displaystyle{ 3^{216}-1}\) jako \(\displaystyle{ (3^{72})^{3}-1^{3}}\) i skorzystać ze wzoru skróconego mnożenia \(\displaystyle{ a^{n}-b^{n}=}\)...
Potem jeszcze trzeba pokazać, że \(\displaystyle{ gcd(3^{216}+3^{144}+3^{72}+1,3^{144}+3^{72}+1)=1}\) - wystarczy jeden krok algorytmu Euklidesa i coś zobaczysz (potęga trójki i coś za Chiny niepodzielnego przez trzy?).

[Medea 2]

Siódme na podstawie piątego: \(\displaystyle{ k = 3}\), \(\displaystyle{ m = 288}\), \(\displaystyle{ n = 216}\) nie wymaga żadnych obliczeń. Wynikiem jest po prostu

\(\displaystyle{ 3^{72} - 1 = 22528399544939174411840147874772640}\).

[Premislav]

Szóste też wynika z piątego (bierzemy \(\displaystyle{ k=2}\)).

[insanis]

Faktycznie, nie pomyślałem, żeby skorzystać po prostu z tego
a jakieś wskazówki co do poprzednich i do tego, z którego skorzystaliśmy?

[Medea 2]

W jedną stronę jest dosyć łatwo, to znaczy: umiem pokazać, że w piątym punkcie liczba po znaku \(\displaystyle{ =}\) dzieli liczbę przed \(\displaystyle{ =}\). Wynika to z tego, że jeżeli \(\displaystyle{ a = bc}\), to \(\displaystyle{ x^{a} - 1^a = x^{bc} - 1^{bc} = (x^b - 1^b)(1 + x^c + \ldots + x^{c(b-1)})}\).

[insanis]

Zrobiłem chyba 3)

Niech \(\displaystyle{ NWD\left( mk,n\right) = a}\) , \(\displaystyle{ NWD\left( k,n\right) = b}\)

\(\displaystyle{ b \Rightarrow a}\)
\(\displaystyle{ b|k \wedge b|n \Rightarrow b|mk \wedge b|n \Rightarrow b|a}\)


\(\displaystyle{ a \Rightarrow b}\)
Skorzystam z tw. Euklidesa, mówiącego, że jeżeli \(\displaystyle{ NWD\left( m,n\right) = 1}\) to \(\displaystyle{ a|mk \Rightarrow a|k}\)
\(\displaystyle{ a|mk \wedge a|n \Rightarrow a|k \wedge a|n \Rightarrow a|b}\)

Proszę o sprawdzenie i ewentualne wskazówki do pozostałych przykładów

[Premislav]

Skorzystam z tw. Euklidesa, mówiącego, że jeżeli \(\displaystyle{ NWD\left( m,n\right) = 1}\) to \(\displaystyle{ a|mk \Rightarrow a|k}\)

Może się czepiam, ale powinno być \(\displaystyle{ n|mk \Rightarrow n|k}\)-- 11 paź 2015, o 17:21 --2) Niech \(\displaystyle{ d=\NWD(km, kn)}\). Czyli \(\displaystyle{ d|km \wedge d|kn \wedge \NWD \left( \frac{km}{d} , \frac{kn}{d} \right)=1}\). To oznacza, że istnieją takie liczby całkowite \(\displaystyle{ c_{1}}\) i \(\displaystyle{ c_{2}}\), że \(\displaystyle{ km=c_{1}d \wedge kn=c_{2}d}\), a więc \(\displaystyle{ c_{1}= \frac{km}{d}\wedge c_{2}= \frac{kn}{d}}\). Ale \(\displaystyle{ \NWD \left( \frac{km}{d} , \frac{kn}{d} \right)=1}\), a więc \(\displaystyle{ \NWD(c_{1},c_{2})=1}\). Gdyby nie było \(\displaystyle{ k|d}\). Oczywiście \(\displaystyle{ k|d}\) (no bez przesady, tego dowodzić nie będę), a więc
\(\displaystyle{ m= \frac{d}{k}c_{1}\wedge n= \frac{d}{k}c_{2}}\) i \(\displaystyle{ \frac{d}{k}}\) jest liczbą całkowitą. Skoro więc \(\displaystyle{ \NWD(c_{1},c_{2})=1}\), to \(\displaystyle{ \NWD(m,n)= \frac{d}{k}}\), czyli \(\displaystyle{ k\cdot \NWD(m,n)=}\)...

[Ponewor]

1) wykonaj algorytm Euklidesa i zobacz co się dzieje po paru krokach
3) masz dobrze, poza tymi momentami gdy robisz napisy \(\displaystyle{ a \Rightarrow b}\), bo niby co ten zapis oznacza? Ale poza tym, wszystko gra.
4) po prostu skorzystaj z 3)
5) zacznij wykonywać algorytm Euklidesa i zaobserwuj, że zacznie się on dziać w wykładnikach

[insanis]

Potrzebuję dalej pomocy z

5) \(\displaystyle{ NWD\left( k^{m}-1,k^{n}-1 \right)=k^{NWD\left( m,n\right)}-1}\) dla każdego \(\displaystyle{ m,n \in Z}\) i \(\displaystyle{ k \ge 2}\)

5) zacznij wykonywać algorytm Euklidesa i zaobserwuj, że zacznie się on dziać w wykładnikach

\(\displaystyle{ k^{m}-1=(k^{n}-1) q_{0}+r_{1}}\)
\(\displaystyle{ k^{n}-1=r_{1}q_{1}+r_{2}}\)

? Nie bardzo wiem jak to zrobić

[Ponewor]

Nie, nie. W algorytmie Euklidesa dzieje się mniej więcej coś takiego:
\(\displaystyle{ \left( k^{m}-1, k^{n}-1\right) = \left(\left( k^{m}-1\right) -\left(k^{n}-1\right), k^{n}-1\right)}\)
Gdy mówię, że należy zaobserwować, że ten algorytm zacznie dziać się w wykładnikach, to mam na myśli pokazanie, że to ostatnie równe jest \(\displaystyle{ \left( k^{m-n}-1, k^{n}-1\right)}\) dla \(\displaystyle{ m>n}\).