ΜΚΔ

Συντονιστής: Γιώργος Ρίζος

Απάντηση
panagiotis iliopoulos

ΜΚΔ

#1

Μη αναγνωσμένη δημοσίευση από panagiotis iliopoulos »

Να αποδείξετε ότι ισχύει gcd(a^{m}-1,a^{n}-1)=a^{gcd(m,n)}-1 για κάθε θετικούς ακεραίους a,m,n και a> 1.
Ετικέτες:
Πρόβλημα
Κορυφή
Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 5573
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: International
Επικοινωνία:
Επικοινωνία Tolaso J Kos

Re: ΜΚΔ

#2

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos »

panagiotis iliopoulos έγραψε: Σάβ Μαρ 10, 2018 8:23 pm Να αποδείξετε ότι ισχύει \gcd(a^{m}-1,a^{n}-1)=a^{\gcd(m,n)}-1 για κάθε θετικούς ακεραίους a,m,n και a> 1.
Σίγουρα είναι για αυτό τον φάκελο; Δίδω μία απόδειξη εκτός φακέλου.

Έστω \displaystyle{\gcd(a^n - 1, a^m - 1) = \lambda} τότε \displaystyle{a^n \equiv 1 \mod \lambda } και \displaystyle{a^m \equiv 1 \mod \lambda }. Κατά συνέπεια \displaystyle{a^{nx + my} \equiv 1\mod \lambda } για κάθε x, y \in \mathbb{Z}. Από τον επεκτεταμένο Ευκλείδιο αλγόριθμο έχουμε ότι \displaystyle{nx + my =\gcd(n,m)} και κατά συνέπεια

\displaystyle{a^{nx + my} \equiv 1 \mod \lambda = a^{\gcd(n,m)} \equiv 1 \mod \lambda \implies\big( a^{\gcd(n,m)} - 1\big) \big| \lambda} Το συμπέρασμα έπεται.

Σημείωση 1: Μήπως είναι άσκηση για το σπίτι από κάποιο μάθημα που παρακολουθείς ;

Σημείωση 2: Γενικότερα, αν \gcd(a, b)=1 και a, b, m , n \in \mathbb{Z}^{+} με a>b τότε:

\displaystyle{\gcd(a^m-b^m,a^n-b^n)=a^{\gcd(m,n)}-b^{\gcd(m,n)}}
Σημείωση 3: Η παραπάνω απόδειξη κυκλοφορεί εκεί έξω . Δεν είναι δική μου.
Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}
Κορυφή
Απάντηση

Επιστροφή στο “Γ ΓΥΜΝΑΣΙΟΥ”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης