Παραγοντοποίηση

Al.Koutsouridis · #1

Να εκφράσετε τον αριθμό 235^2+972^2

ως γινόμενο δυο παραγόντων (χωρίς χρήση υπολογιστή).

Ορέστης Λιγνός · #2

Al.Koutsouridis έγραψε:Να εκφράσετε τον αριθμό ως γινόμενο δυο παραγόντων (χωρίς χρήση υπολογιστή).

Θα χρησιμοποιήσουμε την ταυτότητα Lagrange (a^2+b^2)(x^2+y^2)=(ax+by)^2+(ay-bx)^2

.

Θέτοντας $a=2, \, b=17, \, x=-7, \, y=58$ ,

παίρνουμε 235^2+972^2=(2^2+17^2)(7^2+58^2)

από όπου το ζητούμενο.

#3

Ορέστης Λιγνός έγραψε: παίρνουμε από όπου το ζητούμενο.

Ας την συνεχίσουμε:

Δείξτε ότι η παραγοντοποίηση του Ορέστη είναι η μόνη δυνατή. Εννοείται ότι εξαιρούνται οι τετριμμένες μορφές όπως $235^2+972^2=1\cdot (235^2+972^2)$

KARKAR · #4

Μια ακόμη εφαρμογή : Βρείτε όλα τα ζεύγη διψήφιων φυσικών , των οποίων το γινόμενο να

γράφεται κατά δύο διαφορετικούς τρόπους , ως άθροισμα τετραγώνων δύο διψήφιων φυσικών .

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

Mihalis_Lambrou έγραψε:
Ορέστης Λιγνός έγραψε: παίρνουμε από όπου το ζητούμενο.
Ας την συνεχίσουμε:

Δείξτε ότι η παραγοντοποίηση του Ορέστη είναι η μόνη δυνατή. Εννοείται ότι εξαιρούνται οι τετριμμένες μορφές όπως $235^2+972^2=1\cdot (235^2+972^2)$

Θέλουμε να αποδείξουμε πως οι 2^2+17^2

και

είναι πρώτοι.

Αμφιβάλλω για το αν αυτή είναι η λύση που έχει στο νου του ο κύριος Μιχάλης και μπορεί να έχει κάποια λάθη. Βλέπουμε...

Καταρχάς θα αποδείξουμε πως αν (a, b)=1

,τότε το

διαιρείται μόνο με πρώτους της μορφής 4n+1

. Ισχύει το εξής λήμμα: Αν

πρώτος της μορφής 4n+3

, τότε

αν και μόνο αν p|a

και

. Όμως

, άρα αν ο a^2+b^2

είναι σύνθετος, τότε θα διαιρείται μόνο από πρώτους της μορφής 4n+1

.

Παρεμπιπτόντως οι αριθμοί 2^2+17^2

και

δεν είναι αρκετά μεγάλοι και μπορούμε να δοκιμάσουμε αν διαιρούνται με κάποιον πρώτο της μορφής 4n+1

μέχρι την τετραγωνική τους ρίζα.

Κάνω όμως μια προσπάθεια χωρίς δοκιμές:

Ισχύει ακόμα πως κάθε πρώτος της μορφής 4n+1

είναι άθροισμα

τετραγώνων. Συνεπώς αν γράψουμε το a^2+b^2

στην κανονική του μορφή (αν είναι σύνθετος) τότε θα είναι κάπως έτσι:

$a^2+b^2=(m_1^2+n_1^2)(m_2^2+n_2^2)\cdot ... \cdot (m_k^2+n_k^2)$ . Όμως ισχύει από την ταυτότητα Lagrange

ότι

Επαναλαμβάνοντας αυτή τη διαδικασία προκύπτει ότι a^2+b^2=(m_k^2+n_k^2)(m_l^2+n_l^2)

. Πάλι από την ταυτότητα Lagrange

προκύπτει ότι a^2=(xz+yw)^2

και

Εξετάζουμε με άλλα λόγια αν 17^2=(xz+yw)^2

και αν

δηλαδή αν $xz+yw=\pm 17$ και αν $xw-yz=\pm 2$ , όπου x, y, z, w>0

Έχουμε $xw-yz=\pm 2 \Rightarrow xw=\pm 2+yz \Rightarrow x=\dfrac{\pm 2+yz}{w}$

Ακόμη $xz+yw=\pm 17 \Rightarrow \dfrac{\pm 2z+yz^2}{w}+yw=\pm 17 \Rightarrow \pm 2z+yz^2+yw^2=\pm 17w$ $\Rightarrow y(z^2+w^2)=\pm 2z \pm 17w$ και επειδή (17w, 2z)=1

, προκύπτει ότι y=1

(αν

και

έτσι ώστε

τότε η εξίσωση θα γινόταν $yk^2(m^2+n^2)=k(\pm 2m \pm 17n) \Rightarrow yk(m^2+n^2)=\pm 2m \pm 17n$ όπου προκύπτει ότι yk=1

, δηλαδή

και

).

Άρα πρέπει να ισχύει ότι $xz+w=\pm 17$ και ότι $xw-z=\pm 2$ , δηλαδή $xz^2+zw=\pm 17z$ και ότι $xw^2-zw=\pm 2w$ .

Προσθέτουμε τις δύο σχέσεις κατά μέλη και προκύπτει ότι $x(z^2+w^2)=\pm 17z \pm 2w$ .

Αναγκαστικά x=1

για τον ίδιο λόγο που y=1

.

Άρα έχουμε το σύστημα $w-z=\pm 2$ και $w+z=\pm 17$ το οποίο δεν έχει ακέραιες λύσεις.

Επομένως κάποιος από τους x, y, z, w

είναι ίσος με

και έχουμε τετριμμένη παραγοντοποίηση, όπως 17^2+2^2=(0^2+1^2)(17^2+2^2)

που απορρίπτεται. Συνεπώς 2^2+17^2

πρώτος και με παρόμοιο τρόπο αποδεικνύεται ότι o 7^2+58^2

είναι πρώτος.

#6

Διονύσιος Αδαμόπουλος έγραψε: Θέλουμε να αποδείξουμε πως οι και είναι πρώτοι.
...
Παρεμπιπτόντως οι αριθμοί και δεν είναι αρκετά μεγάλοι και μπορούμε να δοκιμάσουμε αν διαιρούνται με κάποιον πρώτο της μορφής μέχρι την τετραγωνική τους ρίζα.

Ο απευθείας έλεγχος είναι βέβαια χειρονακτικός αλλά για τον 2^2+17^2

που ελέγχουμε μόνο μέχρι τον

, παλεύεται. Για τον 7^2+58^2

πρέπει να πάμε μέχρι τον

, οπότε χρειάζεται να επιστρατεύσουμε Λογιστές. Με την ωραία όμως λύση του Διονύση που απευθύνεται σε Μαθηματικούς, τι να τους κάνουμε τους Λογιστές.

Παραγοντοποίηση

Παραγοντοποίηση

Re: Παραγοντοποίηση

Re: Παραγοντοποίηση

Re: Παραγοντοποίηση

Re: Παραγοντοποίηση

Re: Παραγοντοποίηση

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