Ελάχιστη τιμή φυσικού!

Συντονιστές: achilleas, emouroukos, silouan

Άβαταρ μέλους
Ορέστης Λιγνός
Δημοσιεύσεις: 1065
Εγγραφή: Κυρ Μάιος 08, 2016 7:19 pm
Τοποθεσία: Χαλάνδρι Αττικής

Ελάχιστη τιμή φυσικού!

Μη αναγνωσμένη δημοσίευση #1 από Ορέστης Λιγνός » Σάβ Αύγ 12, 2017 12:58 pm

Να βρείτε τον μικρότερο θετικό ακέραιο αριθμό x έτσι ώστε ο \dfrac{7x^{25}-10}{83} να είναι φυσικός.


Ο καθένας λέει ότι να΄ναι και είναι πάντα σύμφωνος με τον εαυτό του ! 'Ολοι μιλάνε και κανείς δεν ακούει! Ο κόσμος είναι σε νοητική αδράνεια ! Ελένη Γλυκατζή Αρβελέρ

Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7345
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Ελάχιστη τιμή φυσικού!

Μη αναγνωσμένη δημοσίευση #2 από Demetres » Σάβ Αύγ 12, 2017 5:32 pm

Έχουμε 7x^{25} \equiv 10 \bmod 83 και άρα x^{25} \equiv 84 x^{25} \equiv 120 \equiv 37 \bmod 83.

Θέλω να βρω τον αντίστροφο του 25 modulo 82. Τρέχω πρώτα τον Ευκλείδειο αλγόριθμο για να βρω τον μέγιστο κοινό διαιρέτη των 82 και 25. Οι πρώτες δυο γραμμές είναι

\begin{aligned} 82 &= 3 \cdot 25 + 7 \\ 25 &= 3\cdot 7 + 4\end{aligned}

Δεν χρειάζεται να τον συνεχίσω διότι τώρα παρατηρώ ότι 1 = 2 \cdot 4 - 7 και συνεχίζω τρέχοντας τον Ευκλείδιο αλγόριθμο ανάποδα:

\begin{aligned} 1 &= 2 \cdot 4 - 7 \\  &= 2 \cdot (25 - 3 \cdot 7) - 7 \\ &= 2 \cdot 25 - 7 \cdot 7 \\ &= 2 \cdot 25 - 7 \cdot (82 - 3\cdot 25) \\ &= 23 \cdot 25 - 7\cdot 82\end{aligned}

Άρα λοιπόν

\displaystyle{ x \equiv x^{7 \cdot 82 + 1} \equiv x^{23\cdot 25} \equiv 37^{23} \bmod 83}

Για το τελευταίο έχω

\displaystyle{ 37^{23} \equiv \left( \frac{83-9}{2}\right)^{23} \equiv \frac{(-9)^{23}}{2^{23}} \equiv \frac{(-9)(81)^{11}}{2^{23}} \equiv \frac{(-9)(-2)^{11}}{2^{23}} \equiv \frac{9}{2^{12}} \equiv \frac{9}{4096} \bmod 83}

[Εδώ, με τις διαιρέσεις, εννοώ πολλαπλασιασμό με τον ανίστροφο modulo 83. Επιτρέπονται επειδή (2,83)=1.]

Είναι 83 \cdot 50 = 4150 = 4096 + 54. Άρα 4096 \equiv -54 \equiv 29 \bmod 83.

Πάλι μέσω του Ευλείδειου αλγορίθμου βρίσκω 1 = 7\cdot 83 - 20\cdot 29. Άρα

\displaystyle{ x \equiv \frac{9}{4096} \equiv 9(-20) \equiv 180 \equiv -14 \equiv 69 \bmod 83.}

Η μικρότερος λοιπόν θετικός ακέραιος που ικανοποιεί το ζητούμενο είναι ο x=69.


Άβαταρ μέλους
Ορέστης Λιγνός
Δημοσιεύσεις: 1065
Εγγραφή: Κυρ Μάιος 08, 2016 7:19 pm
Τοποθεσία: Χαλάνδρι Αττικής

Re: Ελάχιστη τιμή φυσικού!

Μη αναγνωσμένη δημοσίευση #3 από Ορέστης Λιγνός » Δευ Αύγ 14, 2017 12:28 am

Ευχαριστώ τον Δημήτρη για την λύση του. Δίνω την λύση μου.
Έστω A=\dfrac{7x^{25}-10}{83}. Αφού A \in \mathbb{N}, είναι και A-3 \in \mathbb{N}, οπότε \dfrac{7(x^{25}-37)}{83}
 \in \mathbb{N} \mathop \Rightarrow \limits^{(7,83)=1} x^{25} \equiv 37 \pmod {83}.

Είναι x^{75}=(x^{25})^3 \equiv 37^{23} \equiv 23 \pmod {83} \Rightarrow x^{83} \equiv 23x^8 \pmod{83} (1).

Από Θ. Fermat x^{83} \equiv x \pmod {83} (2).

Από (1), (2), 23x^8 \equiv x \pmod {83} \Rightarrow x(23x^7-1) \equiv 0 \pmod {83} (3).

Αν x \equiv 0 \pmod {83}, είναι 7x^{25} \equiv 0 \neq 10 \pmod {83}, άτοπο, οπότε (3) \Rightarrow 23x^7 \equiv 1 \pmod {83}.

Είναι B=\dfrac{23x^7-1}{83}  \in \mathbb{N} \Rightarrow B-18 \in \mathbb{N} \Rightarrow \dfrac{23(x^7-65)}{83} \in \mathbb{N} \Rightarrow x^7 \equiv 65 \pmod {83}, και

37 \equiv x^{25}=x^{21} \cdot x^4=(x^7)^3 \cdot x^4 \equiv 61x^4 \pmod {83} \Rightarrow 61x^4 \equiv 37 \pmod {83}


και με το προηγούμενο τέχνασμα x^4 \equiv 70 \pmod {83} \Rightarrow x^{24} \equiv (70)^6 \equiv 27 \pmod {83 } \Rightarrow

x^{25} \equiv  27x  \pmod {83} \Rightarrow 27x \equiv 37 \pmod {83} \Rightarrow x \equiv 69 \pmod {83}, οπότε \boxed{\min x=69}.


Ο καθένας λέει ότι να΄ναι και είναι πάντα σύμφωνος με τον εαυτό του ! 'Ολοι μιλάνε και κανείς δεν ακούει! Ο κόσμος είναι σε νοητική αδράνεια ! Ελένη Γλυκατζή Αρβελέρ

Επιστροφή σε “Άλγεβρα - Προχωρημένο Επίπεδο (Seniors)”

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

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