Ασκήσεις Θεωρίας Αριθμών

stranger · #1

1) (Δύσκολη) Λύστε στο $\mathbb{Z}$ την εξίσωση x^2+7=2^n

Nikitas K. · #2

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

$x^2+7=2^n \Leftrightarrow x^2 = 1\underbrace{00\dots 0}_{n} _2 - 11_2 = \underbrace{11\dots 1}_{n-3}001_2$

Θέτοντας, $c := n-3 \wedge x_c := |x|$ , οπότε από την αρχική εξίσωση παίρνουμε την παρακάτω:

$\displaystyle x_c ^2 = \underbrace{11\dots 1}_{c}001_2$ , προφανώς το x_c

πρέπει να είναι περιττός.

Θέτοντας, x_c := 2k+1

, μετά από τις πράξεις καταλήγουμε ότι:
$\displaystyle \frac{k(k+1)}{2} = \underbrace{11\dots 1}_{c}_2$ , Triangular Mersenne numbers
$\displaystyle k(k+1) = \underbrace{11\dots 1}_{c}0_2$ ,
Έστω, η συνάρτηση

να επιστρέφει το πλήθος των ψηφίων της δυαδικής αναπαράστασης της εισόδου.
$\displaystyle D(k) = \left \lceil \frac{c+1}{2} \right \rceil = \left\{\begin{matrix} \frac{c}{2} + 1 & c ~ mod ~ 2 = 0 \\ \frac{c+1}{2} & c ~ mod ~ 2 = 1 \end{matrix}\right.$

Αν είναι άρτιος, τότε , οπότε .
Θέτω,
Επιλύοντας τα συστήματα κάθε περίπτωσης, γίνεται να αποτιμηθεί ο αριθμός .
- Αν είναι άρτιος, τότε $k_0 = 0\Rightarrow k_1 = 1\Rightarrow k_2 = 0\Rightarrow k_3 = 1\Rightarrow k_4 = 1 \Rightarrow k_5 = 0\Rightarrow k_6 = 1\Rightarrow k_7 = 0\Rightarrow \dots \Rightarrow k_\lambda = 1$
- Αν είναι περιττός, τότε $k_0 = 1 \Rightarrow \dots$

Αν είναι περιττός, τότε , οπότε .
Θέτω,
Επιλύοντας τα συστήματα κάθε περίπτωσης, γίνεται να αποτιμηθεί ο αριθμός .
- Αν είναι άρτιος, τότε $k_0 = 0\Rightarrow \dots$
- Αν είναι περιττός, τότε $k_0 = 1 \Rightarrow \dots$

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Nikitas K. · #3

Χαίρετε,

Έχοντας φτάσει ως το παρακάτω σημείο, υπάρχει κάποιος τρόπος να συνεχίστεί ο υπολογισμός όλων των δυαδικών ψηφίων του αριθμού

έτσι, ώστε να λάβουμε την μορφή που θα έχει ο αριθμός

σε κάθε περίπτωση;

Nikitas K. έγραψε: ↑
Δευ Απρ 22, 2024 4:00 pm
$\displaystyle k(k+1) = \underbrace{11\dots 1}_{c}0_2$ ,
Έστω, η συνάρτηση να επιστρέφει το πλήθος των ψηφίων της δυαδικής αναπαράστασης της εισόδου.
$\displaystyle D(k) = \left \lceil \frac{c+1}{2} \right \rceil = \left\{\begin{matrix} \frac{c}{2} + 1 & c ~ mod ~ 2 = 0 \\ \frac{c+1}{2} & c ~ mod ~ 2 = 1 \end{matrix}\right.$

Αν είναι άρτιος, τότε $\exists\lambda\in\mathbb{N} ~ c = 2\lambda$ , οπότε $D(k) = \lambda + 1$ .
Θέτω, $k:= (k_\lambda k_{\lambda - 1} k_{\lambda-2}\dots k_1 k_0) _2$
Επιλύοντας τα $\lambda + 1$ συστήματα κάθε περίπτωσης, γίνεται να αποτιμηθεί ο αριθμός .
Αν είναι άρτιος, τότε $k_0 = 0\Rightarrow k_1 = 1\Rightarrow k_2 = 0\Rightarrow k_3 = 1\Rightarrow k_4 = 1 \Rightarrow k_5 = 0\Rightarrow k_6 = 1\Rightarrow k_7 = 0\Rightarrow \dots \Rightarrow k_\lambda = 1$

Αν είναι περιττός, τότε $k_0 = 1 \Rightarrow \dots$

Αν είναι περιττός, τότε $\exists\lambda\in\mathbb{N} ~ c = 2\lambda+1$ , οπότε $D(k) = \lambda + 1$ .
Θέτω, $k:= (k_\lambda k_{\lambda - 1} k_{\lambda-2}\dots k_1 k_0) _2$
Επιλύοντας τα $\lambda + 1$ συστήματα κάθε περίπτωσης, γίνεται να αποτιμηθεί ο αριθμός .
Αν είναι άρτιος, τότε $k_0 = 0\Rightarrow \dots$

Αν είναι περιττός, τότε $k_0 = 1 \Rightarrow \dots$

stranger · #4

Nikitas K. έγραψε: ↑
Σάβ Απρ 27, 2024 12:07 pm
Χαίρετε,

Έχοντας φτάσει ως το παρακάτω σημείο, υπάρχει κάποιος τρόπος να συνεχίστεί ο υπολογισμός όλων των δυαδικών ψηφίων του αριθμού έτσι, ώστε να λάβουμε την μορφή που θα έχει ο αριθμός σε κάθε περίπτωση;

Nikitas K. έγραψε: ↑
Δευ Απρ 22, 2024 4:00 pm
$\displaystyle k(k+1) = \underbrace{11\dots 1}_{c}0_2$ ,
Έστω, η συνάρτηση να επιστρέφει το πλήθος των ψηφίων της δυαδικής αναπαράστασης της εισόδου.
$\displaystyle D(k) = \left \lceil \frac{c+1}{2} \right \rceil = \left\{\begin{matrix} \frac{c}{2} + 1 & c ~ mod ~ 2 = 0 \\ \frac{c+1}{2} & c ~ mod ~ 2 = 1 \end{matrix}\right.$

Αν είναι άρτιος, τότε $\exists\lambda\in\mathbb{N} ~ c = 2\lambda$ , οπότε $D(k) = \lambda + 1$ .
Θέτω, $k:= (k_\lambda k_{\lambda - 1} k_{\lambda-2}\dots k_1 k_0) _2$
Επιλύοντας τα $\lambda + 1$ συστήματα κάθε περίπτωσης, γίνεται να αποτιμηθεί ο αριθμός .
Αν είναι άρτιος, τότε $k_0 = 0\Rightarrow k_1 = 1\Rightarrow k_2 = 0\Rightarrow k_3 = 1\Rightarrow k_4 = 1 \Rightarrow k_5 = 0\Rightarrow k_6 = 1\Rightarrow k_7 = 0\Rightarrow \dots \Rightarrow k_\lambda = 1$

Αν είναι περιττός, τότε $k_0 = 1 \Rightarrow \dots$

Αν είναι περιττός, τότε $\exists\lambda\in\mathbb{N} ~ c = 2\lambda+1$ , οπότε $D(k) = \lambda + 1$ .
Θέτω, $k:= (k_\lambda k_{\lambda - 1} k_{\lambda-2}\dots k_1 k_0) _2$
Επιλύοντας τα $\lambda + 1$ συστήματα κάθε περίπτωσης, γίνεται να αποτιμηθεί ο αριθμός .
Αν είναι άρτιος, τότε $k_0 = 0\Rightarrow \dots$

Αν είναι περιττός, τότε $k_0 = 1 \Rightarrow \dots$

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

miltosk · #5

stranger έγραψε: ↑
Σάβ Απρ 20, 2024 10:40 pm
1) (Δύσκολη) Λύστε στο $\mathbb{Z}$ την εξίσωση

Ας γράψω τι σκέφτηκα, αλλα δεν έχω και πολύ χρόνο να το αναλύσω, το αφήνω ως ιδέα μήπως προχωρήσει κάπως.
Αρχικά, για

άρτιο είναι σχετικά απλό (διαφορά τετραγώνων).
Τώρα, για

περιττό έχουμε:
$x^2-2\cdot 2^{2t}= -7, t=\frac{n}{2}$
Τώρα, αυτό θυμίζει γενικευμένη Pell (d=2, N=-7).
Αν θέλουμε $N<\sqrt{d}$ , τότε απλά τη γράφουμε στη μορφή:
$x^2-128\cdot 2^{2q}, q=\frac{n-7}{2}$ , σαφώς με τις κατάλληλες υποθέσεις.
Έχουμε: 11^2-128=-7

, μία ας τη θεωρήσουμε πρωταρχική λύση των εξισώσεων x^2-2y^2=-7, x^2-128y^2=-7

.
Ακόμη, η εξίσωση x^2-2y^2=1

έχει λύση

Τώρα για την $x^2-128y^2=1 \Rightarrow (x-1)(x+1) = 128y^2 \Rightarrow d(d+1)=32y^2$
Οπότε γενικά θα πάρουμε $x=2\cdot (32d+1), x=2\cdot (32d-1)$ . Μάλλον λίγο ζόρι να βρούμε πρωταρχική λύση εδώ για να πάρουμε μετά τον αναδρομικό αλγόριθμο.
Μια άλλη ιδέα θα ήταν:
$(x-2^t\cdot \sqrt{2})(x+2^t\cdot \sqrt{2})=-7$ .
Γενικά το $Z[i\sqrt{2}]$ είναι UFD, το παραπάνω βέβαια είναι στο $Z[\sqrt{2}]$ , και δεν είμαι σίγουρος αν μπορούμε να δουλέψουμε ανάλογα (το 7 μάλιστα δεν είναι πρώτος σε αυτό τον δακτύλιο). Έχω την εντύπωση πως ο τελευταίος δακτύλιος είναι UFD, αν ισχύουν αυτά μπορώ να προχωρήσω σε λύση, αλλιώς μάλλον πρέπει να αλλάξουμε προσέγγιση.

Ασκήσεις Θεωρίας Αριθμών

Ασκήσεις Θεωρίας Αριθμών

Re: Ασκήσεις Θεωρίας Αριθμών

Re: Ασκήσεις Θεωρίας Αριθμών

Re: Ασκήσεις Θεωρίας Αριθμών

Re: Ασκήσεις Θεωρίας Αριθμών

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