NWD a liczby względnie pierwsze

[kluczyk]

Wyznacz \(\displaystyle{ NWD(5^{m}+7^{m} , 5^{n}+7^{n})}\) , gdzie \(\displaystyle{ m}\) i \(\displaystyle{ n}\) są liczbami naturalnymi względnie pierwszymi.

[BettyBoo]

Lemat: Niech \(\displaystyle{ a,b,r}\) będą naturalne, \(\displaystyle{ q}\) całkowite nieujemne oraz niech \(\displaystyle{ a>b}\).
Jeśli \(\displaystyle{ a=bq+r}\), to \(\displaystyle{ NWD(7^a+5^a,7^b+5^b)|(7^r+5^r)}\)

Dowód:
(1) Niech \(\displaystyle{ q}\) będzie parzyste. Wtedy

\(\displaystyle{ 7^a+5^a=(7^b+5^b)(7^{a-b}-7^{a-2b}5^b+\cdots -7^{a-qb}5^{(q-1)b})+7^{a-qb}5^{qb}+5^a}\)

czyli \(\displaystyle{ 7^a+5^a=(7^b+5^b)t+5^{a-r}(7^r+5^r)}\)

Zatem \(\displaystyle{ NWD(7^a+5^a,7^b+5^b)|5^{a-r}(7^r+5^r)}\). Ponieważ dla dowolnego naturalnego \(\displaystyle{ m}\) mamy \(\displaystyle{ 5^m+7^m\equiv_52^m\not\equiv_5 0}\), to z Lematu Euklidesa wynika, że

\(\displaystyle{ NWD(7^a+5^a,7^b+5^b)|(7^r+5^r)}\)


(2) Niech \(\displaystyle{ q}\) będzie nieparzyste. Wtedy \(\displaystyle{ a=b(q-1)+(b+r)}\) i z punktu (1) mamy, że \(\displaystyle{ NWD(7^a+5^a,7^b+5^b)|(7^{b+r}+5^{b+r})}\). Dalej, ponieważ

\(\displaystyle{ (7^b+5^b)(7^r+5^r)=7^{b+r}+5^{b+r}+5^{b-r}7^{b-r}(7^r+5^r)}\)

oraz dla dowolnego naturalnego \(\displaystyle{ m}\) mamy

\(\displaystyle{ 5^m+7^m\equiv_7(-2)^m\not\equiv_7 0,\quad 5^m+7^m\not\equiv_50}\) to z Lematu Euklidesa wynika, że

\(\displaystyle{ NWD(7^a+5^a,7^b+5^b)|(7^r+5^r)\ \square}\)

Dowód dla NWD
Ponieważ \(\displaystyle{ m}\) i \(\displaystyle{ n}\) są względnie pierwsze, to z algorytmu Euklidesa wynika, że stosując powyższy lemat odpowiednią ilość razy otrzymujemy \(\displaystyle{ NWD(7^m+5^m,7^n+5^n)|12}\).

Ponadto jeśli:
(a) \(\displaystyle{ m}\) jest parzyste, a \(\displaystyle{ n}\) nieparzyste, to wówczas \(\displaystyle{ 7^m+5^m,7^n+5^n}\) są parzyste oraz

\(\displaystyle{ 5^m+7^m\equiv_34^\frac{m}{2}+1\equiv_3 1+1\not\equiv_30,\quad 5^m+7^m\equiv_41+9^\frac{m}{2}\equiv_41+1\not\equiv_40}\),

zatem \(\displaystyle{ NWD(7^a+5^a,7^b+5^b)=2}\)

(b) \(\displaystyle{ m,n}\) są nieparzyste, to wówczas

\(\displaystyle{ 5^m+7^m\equiv_{12} 5(25)^\frac{m-1}{2}+7(49)^\frac{m-1}{2}\equiv_{12}0,\quad 5^n+7^n\equiv_{12}0}\),

zatem \(\displaystyle{ NWD(7^a+5^a,7^b+5^b)=12}\).

Pozdrawiam.

[frej]

W języku kongruencji dowód jest krótszy w zapisie.
Niech \(\displaystyle{ d|5^m+7^m \; \; d|5^n+7^n}\). Wtedy
\(\displaystyle{ \left( \frac{5}{7} \right)^n \equiv \left( \frac{5}{7} \right)^m \equiv -1 \pmod{d}}\) skąd
\(\displaystyle{ \left( \frac{5}{7} \right)^{(n,m)} \equiv \left( \frac{5}{7} \right)^1 \equiv -1 \pmod{d}}\)
czyli
\(\displaystyle{ \boxed{d|12}}\)

Jeśli \(\displaystyle{ 2|m}\) to \(\displaystyle{ d|4}\), bo \(\displaystyle{ \left( \frac{-1}{3} \right)=-1}\). W tym przypadku \(\displaystyle{ d=2}\), bo \(\displaystyle{ 7^m+5^m\equiv 2 \pmod{4}}\).
Jeśli \(\displaystyle{ 2\nmid n,m}\) to \(\displaystyle{ d=12}\), bo \(\displaystyle{ 5 \equiv -7 \pmod{12} \Rightarrow 5 \equiv -7 \pmod{4} \; \wedge \; 5 \equiv -7 \pmod{3}}\)

[patry93]

frej - skąd się wzięły dwie pierwsze kongruencje? Myślałem, że w kongr. można operować jedynie na liczbach całkowitych...

[frej]

To nie są ułamki. \(\displaystyle{ \frac{1}{a}=a^{-1}}\) rozumiem jako element odwrotny modulo

zaś \(\displaystyle{ \left( \frac{-1}{3} \right)}\) jest symbolem Lagreange'a

[BettyBoo]

No fakt..trochę za mało operowałam na kongruencjach, a tak to ślicznie prościutko wychodzi

frej, symbol Legendre'a Nota bene nie trzeba go tu używać, wystarczy Lemat Euklidesa.

Pozdrawiam.

[frej]

Nigdy nie wiedziałem jak poprawnie napisać to nazwisko. Symbol Legendre'a jest po prostu krótszym zapisem sformułowania, że \(\displaystyle{ -1}\) jest nieresztą kwadratową modulo \(\displaystyle{ 3}\), co pokazuje, że dla parzystego \(\displaystyle{ m}\) nie zachodzi podzielność \(\displaystyle{ 3|5^m+7^m}\)