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

harrisp · #1

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

που ικανοποιούν την:

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

harrisp · #2

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

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

Επαναφορά!

#3

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

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

.

Αν υποθέσουμε ότι $\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|n

και

πράγμα άτοπο.

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

$\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\}}}$ .

harrisp · #4

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

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

Αν υποθέσουμε ότι $\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).}$ Ειδικότερα, ο είναι περιττός, οπότε από το μικρό θεώρημα του 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)}$ και αν πάρουμε έναν πρώτο διαιρέτη του , τότε θα έχουμε ότι και πράγμα άτοπο.

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

$\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}$ και .

Αν ο $\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\}}}$ .

Σας ευχαριστώ πολύ για τις όμορφες και περιποιημένες λύσεις που δίνετε!

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

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

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

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

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

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