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

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

Να βρείτε τον μικρότερο θετικό ακέραιο αριθμό

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

#2

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

Θέλω να βρω τον αντίστροφο του

modulo

. Τρέχω πρώτα τον Ευκλείδειο αλγόριθμο για να βρω τον μέγιστο κοινό διαιρέτη των

και

. Οι πρώτες δυο γραμμές είναι

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

. Επιτρέπονται επειδή (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

.

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

Ευχαριστώ τον Δημήτρη για την λύση του. Δίνω την λύση μου.
Έστω $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}$ .

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

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

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

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

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