Διοφαντική με την συνάρτηση φ του Euler

Συντονιστές: cretanman, silouan, rek2

harrisp
Δημοσιεύσεις: 547
Εγγραφή: Σάβ Μαρ 28, 2015 8:49 pm

Διοφαντική με την συνάρτηση φ του Euler

#1

Μη αναγνωσμένη δημοσίευση από harrisp » Παρ Ιουν 16, 2017 2:28 pm

Βρείτε όλα τα ζεύγη θετικών ακεραίων (m,n) που ικανοποιούν την:

2^n+(n-\phi (n) -1)!=n^m+1



Λέξεις Κλειδιά:
harrisp
Δημοσιεύσεις: 547
Εγγραφή: Σάβ Μαρ 28, 2015 8:49 pm

Re: Διοφαντική με την συνάρτηση φ του Euler

#2

Μη αναγνωσμένη δημοσίευση από harrisp » Σάβ Ιουν 17, 2017 5:15 pm

ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ έγραψε:Βρείτε όλα τα ζεύγη θετικών ακεραίων (m,n) που ικανοποιούν την:

2^n+(n-\phi (n) -1)!=n^m+1
Επαναφορά!


Άβαταρ μέλους
emouroukos
Συντονιστής
Δημοσιεύσεις: 1417
Εγγραφή: Δευ Δεκ 22, 2008 1:27 pm
Τοποθεσία: Αγρίνιο

Re: Διοφαντική με την συνάρτηση φ του Euler

#3

Μη αναγνωσμένη δημοσίευση από emouroukos » Τρί Ιουν 20, 2017 10:58 pm

Πρώτα απ' όλα, παρατηρούμε ότι πρέπει n \ge2.

Έστω \displaystyle{{p_1} < {p_2} <  \cdots  < {p_k}} οι πρώτοι διαιρέτες του αριθμού n.

Αν υποθέσουμε ότι \displaystyle{{p_1} \le n - \varphi \left( n \right) - 1,} τότε \displaystyle{{p_1}|\left( {n - \varphi \left( n \right) - 1} \right)!} και \displaystyle{{p_1}|{n^m},} οπότε από τη δοσμένη σχέση προκύπτει ότι \displaystyle{{2^n} \equiv 1\left( {\bmod {p_1}} \right).} Ειδικότερα, ο p_1 είναι περιττός, οπότε από το μικρό θεώρημα του Fermat έχουμε ότι \displaystyle{{2^{{p_1} - 1}} \equiv 1\left( {\bmod {p_1}} \right).} Επομένως, αν \displaystyle{d = {\rm{or}}{{\rm{d}}_{{p_1}}}\left( 2 \right),} τότε \displaystyle{d|\left( {{p_1} - 1,n} \right)} και αν πάρουμε έναν πρώτο διαιρέτη q του d>1, τότε θα έχουμε ότι q|n και q<p_1, πράγμα άτοπο.

Είναι γνωστό ότι

\displaystyle{\varphi \left( n \right)  = n\prod\limits_{i = 1}^k {\left( {1 - \frac{1}{{{p_i}}}} \right)} ,}

οπότε

\displaystyle{n - \varphi \left( n \right) - 1 = n\left[ {1 - \prod\limits_{i = 1}^k {\left( {1 - \frac{1}{{{p_i}}}} \right)} } \right] - 1.}

Επειδή \displaystyle{0 < 1 - \frac{1}{{{p_i}}} < 1} για κάθε \displaystyle{i \in \left\{ {1,2, \ldots ,k} \right\},} έχουμε ότι:

\displaystyle{\prod\limits_{i = 2}^k {\left( {1 - \frac{1}{{{p_i}}}} \right)}  < 1 \Rightarrow \prod\limits_{i = 1}^k {\left( {1 - \frac{1}{{{p_i}}}} \right)}  < 1 - \frac{1}{{{p_1}}} \Rightarrow 1 - \prod\limits_{i = 1}^k {\left( {1 - \frac{1}{{{p_i}}}} \right)}  > \frac{1}{{{p_1}}},}

οπότε

\displaystyle{n - \varphi \left( n \right) - 1 > \frac{n}{{{p_1}}} - 1 \Longrightarrow \boxed{n - \varphi \left( n \right) - 1 \ge \frac{n}{{{p_1}}}} \bf \color{red}\left( 1 \right).

Παρατηρούμε τώρα ότι:

\bullet \displaystyle{k > 1 \Rightarrow \frac{n}{{{p_1}}} \ge \frac{{p_1^{{v_{{p_1}}}\left( n \right)}{p_2}}}{{{p_1}}} > p_1^{{v_{{p_1}}}\left( n \right)} \ge {p_1},}

\bullet \displaystyle{{v_{{p_1}}}\left( n \right) > 2 \Rightarrow \frac{n}{{{p_1}}} \ge \frac{{p_1^{{v_{{p_1}}}\left( n \right)}}}{{{p_1}}} > \frac{{p_1^2}}{{{p_1}}} = {p_1}.}

Συνεπώς, από τη σχέση \bf \color{red}\left( 1 \right) προκύπτει ότι αν \displaystyle{k > 1} ή \displaystyle{{v_{{p_1}}}\left( n \right) > 2,} τότε \displaystyle{n - \varphi \left( n \right) - 1 > {p_1}} και από τα παραπάνω καταλήγουμε σε άτοπο.

Έτσι, πρέπει \displaystyle{k = 1} και \displaystyle{{v_{{p_1}}}\left( n \right) \le 2,} δηλαδή \displaystyle{n = {p_1}} ή \displaystyle{{n = p_1^2}.}

\bullet Αν \displaystyle{n = {p_1},} τότε η δοσμένη σχέση γράφεται ισοδύναμα \displaystyle{{2^{{p_1}}} = p_1^m,} οπότε \displaystyle{{p_1} = n = m = 2.}

\bullet Αν \displaystyle{{n = p_1^2},} τότε η δοσμένη σχέση γράφεται ισοδύναμα \displaystyle{{2^{p_1^2}} + \left( {{p_1} - 1} \right)! = p_1^{2m} + 1} \bf \color{red}\left( 2 \right).

Αν \displaystyle{{p_1} = 2,} τότε η σχέση \bf \color{red}\left( 2 \right) δίνει ότι \displaystyle{m = 2} και n=4.

Αν ο \displaystyle{{{p_1}}} είναι περιττός, τότε \displaystyle{p_1^2 \equiv 1\left( {\bmod 4} \right),} οπότε η σχέση \bf \color{red}\left( 2 \right) δίνει ότι \displaystyle{\left( {{p_1} - 1} \right)! \equiv 2\left( {\bmod 4} \right).} Αλλά για \displaystyle{{{p_1} \ge 5}} είναι \displaystyle{\left( {{p_1} - 1} \right)! \equiv 0\left( {\bmod 4} \right),} οπότε πρέπει \displaystyle{{{p_1} = 3}.} Τότε, η σχέση \bf \color{red}\left( 2 \right) δίνει ότι \displaystyle{513 = {3^{2m}},} που είναι άτοπο.

Ώστε, η δοσμένη εξίσωση έχει τις λύσεις \displaystyle{\boxed{\left( {m,n} \right) \in \left\{ {\left( {2,2} \right),\left( {2,4} \right)} \right\}}}.


Βαγγέλης Μουρούκος

Erro ergo sum.
harrisp
Δημοσιεύσεις: 547
Εγγραφή: Σάβ Μαρ 28, 2015 8:49 pm

Re: Διοφαντική με την συνάρτηση φ του Euler

#4

Μη αναγνωσμένη δημοσίευση από harrisp » Τετ Ιουν 21, 2017 12:31 am

emouroukos έγραψε:Πρώτα απ' όλα, παρατηρούμε ότι πρέπει n \ge2.

Έστω \displaystyle{{p_1} < {p_2} <  \cdots  < {p_k}} οι πρώτοι διαιρέτες του αριθμού n.

Αν υποθέσουμε ότι \displaystyle{{p_1} \le n - \varphi \left( n \right) - 1,} τότε \displaystyle{{p_1}|\left( {n - \varphi \left( n \right) - 1} \right)!} και \displaystyle{{p_1}|{n^m},} οπότε από τη δοσμένη σχέση προκύπτει ότι \displaystyle{{2^n} \equiv 1\left( {\bmod {p_1}} \right).} Ειδικότερα, ο p_1 είναι περιττός, οπότε από το μικρό θεώρημα του Fermat έχουμε ότι \displaystyle{{2^{{p_1} - 1}} \equiv 1\left( {\bmod {p_1}} \right).} Επομένως, αν \displaystyle{d = {\rm{or}}{{\rm{d}}_{{p_1}}}\left( 2 \right),} τότε \displaystyle{d|\left( {{p_1} - 1,n} \right)} και αν πάρουμε έναν πρώτο διαιρέτη q του d>1, τότε θα έχουμε ότι q|n και q<p_1, πράγμα άτοπο.

Είναι γνωστό ότι

\displaystyle{\varphi \left( n \right)  = n\prod\limits_{i = 1}^k {\left( {1 - \frac{1}{{{p_i}}}} \right)} ,}

οπότε

\displaystyle{n - \varphi \left( n \right) - 1 = n\left[ {1 - \prod\limits_{i = 1}^k {\left( {1 - \frac{1}{{{p_i}}}} \right)} } \right] - 1.}

Επειδή \displaystyle{0 < 1 - \frac{1}{{{p_i}}} < 1} για κάθε \displaystyle{i \in \left\{ {1,2, \ldots ,k} \right\},} έχουμε ότι:

\displaystyle{\prod\limits_{i = 2}^k {\left( {1 - \frac{1}{{{p_i}}}} \right)}  < 1 \Rightarrow \prod\limits_{i = 1}^k {\left( {1 - \frac{1}{{{p_i}}}} \right)}  < 1 - \frac{1}{{{p_1}}} \Rightarrow 1 - \prod\limits_{i = 1}^k {\left( {1 - \frac{1}{{{p_i}}}} \right)}  > \frac{1}{{{p_1}}},}

οπότε

\displaystyle{n - \varphi \left( n \right) - 1 > \frac{n}{{{p_1}}} - 1 \Longrightarrow \boxed{n - \varphi \left( n \right) - 1 \ge \frac{n}{{{p_1}}}} \bf \color{red}\left( 1 \right).

Παρατηρούμε τώρα ότι:

\bullet \displaystyle{k > 1 \Rightarrow \frac{n}{{{p_1}}} \ge \frac{{p_1^{{v_{{p_1}}}\left( n \right)}{p_2}}}{{{p_1}}} > p_1^{{v_{{p_1}}}\left( n \right)} \ge {p_1},}

\bullet \displaystyle{{v_{{p_1}}}\left( n \right) > 2 \Rightarrow \frac{n}{{{p_1}}} \ge \frac{{p_1^{{v_{{p_1}}}\left( n \right)}}}{{{p_1}}} > \frac{{p_1^2}}{{{p_1}}} = {p_1}.}

Συνεπώς, από τη σχέση \bf \color{red}\left( 1 \right) προκύπτει ότι αν \displaystyle{k > 1} ή \displaystyle{{v_{{p_1}}}\left( n \right) > 2,} τότε \displaystyle{n - \varphi \left( n \right) - 1 > {p_1}} και από τα παραπάνω καταλήγουμε σε άτοπο.

Έτσι, πρέπει \displaystyle{k = 1} και \displaystyle{{v_{{p_1}}}\left( n \right) \le 2,} δηλαδή \displaystyle{n = {p_1}} ή \displaystyle{{n = p_1^2}.}

\bullet Αν \displaystyle{n = {p_1},} τότε η δοσμένη σχέση γράφεται ισοδύναμα \displaystyle{{2^{{p_1}}} = p_1^m,} οπότε \displaystyle{{p_1} = n = m = 2.}

\bullet Αν \displaystyle{{n = p_1^2},} τότε η δοσμένη σχέση γράφεται ισοδύναμα \displaystyle{{2^{p_1^2}} + \left( {{p_1} - 1} \right)! = p_1^{2m} + 1} \bf \color{red}\left( 2 \right).

Αν \displaystyle{{p_1} = 2,} τότε η σχέση \bf \color{red}\left( 2 \right) δίνει ότι \displaystyle{m = 2} και n=4.

Αν ο \displaystyle{{{p_1}}} είναι περιττός, τότε \displaystyle{p_1^2 \equiv 1\left( {\bmod 4} \right),} οπότε η σχέση \bf \color{red}\left( 2 \right) δίνει ότι \displaystyle{\left( {{p_1} - 1} \right)! \equiv 2\left( {\bmod 4} \right).} Αλλά για \displaystyle{{{p_1} \ge 5}} είναι \displaystyle{\left( {{p_1} - 1} \right)! \equiv 0\left( {\bmod 4} \right),} οπότε πρέπει \displaystyle{{{p_1} = 3}.} Τότε, η σχέση \bf \color{red}\left( 2 \right) δίνει ότι \displaystyle{513 = {3^{2m}},} που είναι άτοπο.

Ώστε, η δοσμένη εξίσωση έχει τις λύσεις \displaystyle{\boxed{\left( {m,n} \right) \in \left\{ {\left( {2,2} \right),\left( {2,4} \right)} \right\}}}.
Σας ευχαριστώ πολύ για τις όμορφες και περιποιημένες λύσεις που δίνετε!


Απάντηση

Επιστροφή σε “Θεωρία Αριθμών - Προχωρημένο Επίπεδο (Seniors)”

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

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