FMID

harrisp · #1

Να λυθεί στους μη αρνητικούς ακεραίους η εξίσωση:

2^x=xy+1

Για μαθητές μέχρι και την νίκη της Εθνικής μας ομάδας το Σάββατο.

Διονύσιος Αδαμόπουλος · #2

Έστω

.

Προφανώς

περιττός.

Πρέπει να ισχύει ότι:

$2^x \equiv 1 \pmod{x}$

Παίρνουμε τον ελάχιστο πρώτο που διαιρεί το

, έστω

. Έχουμε πως $p\geq 3$ .

Πρέπει:

$2^x \equiv 1 \pmod{p}$

Ακόμη έστω

ο ελάχιστος ακέραιος έτσι ώστε $2^d \equiv 1 \pmod{p}$ .

Από τον ορισμό του order

έχουμε πως d|x

.

Από το μικρό θεώρημα του Fermat

έχουμε πως $2^{p-1} \equiv 1 \pmod{p}$ , άρα d|p-1

Επομένως

.

Όμως

, καθώς ο

είναι μικρότερος από οποιονδήποτε πρώτο διαιρέτη του

.

Επομένως d=1

και έχουμε πως $2^1 \equiv 1 \pmod{p}\Leftrightarrow p|1$ , άτοπο.

Αν x=0

, τότε έχουμε τις λύσεις (x, y)=(0, y)

Αν

, τότε έχουμε τις λύσεις (x, y)=(1, 1)

.

JimNt. · #3

ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ έγραψε:Να λυθεί στους μη αρνητικούς ακεραίους η εξίσωση:

Για μαθητές μέχρι και την νίκη της Εθνικής μας ομάδας το Σάββατο.

Προφανείς λύσεις : (x,y)=(0,f)

$f \in \mathbb{N}$ , (1,1)

. Θα δείξουμε ότι είναι και η μοναδικές. Έστω πρώτος p|x

$\Leftrightarrow$ x=pn

. Πρέπει $p|2^{pn}-1=(2^{n})^{p}-1$ . Ωστόσο από FLT

ισχύει $p|(2^{n})^{p-1}-1$ . Συνεπώς, $p|(2^{n})^{(p,p-1)}-1=1$ , άτοπο. (Με πρόλαβαν....)

harrisp · #4

Πολύ Ωραία

Ας δούμε τωρα λύση και με FMID...

#5

ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ έγραψε: Ας δούμε τωρα λύση και με FMID...

Δηλαδή;

JimNt. · #6

Άπειρη κάθοδος του Fermat.

harrisp · #7

Demetres έγραψε:
ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ έγραψε: Ας δούμε τωρα λύση και με FMID...
Δηλαδή;

Fermat's Method of Infinite Descent