Determinare le soluzioni intere positive di
$ 19^{19}=m^3+n^4 $
[E' troppo facile! (by SimoTheWolf) - sconsigliato agli esperti]
Terze, quarte e diciannovesime potenze.
, potresti postare la soluzione di questo problema? Nessun problema, anche se speravo che qualcuno lo facesse ... se pur per me non è troppo facile (come altri dissero), cmq non mi sembrava folle.
Allora ... riscriviamo tutto modulo 13 ...
$ 19\equiv 6\ (\bmod 13) $ e le sue potenze fanno così :
$ 19^0\equiv 1\quad 19^1\equiv 6\quad 19^2\equiv10\quad19^3\equiv8\quad19^4\equiv9\quad19^5\equiv2\quad19^6\equiv-1 $
quindi $ 19^{19}\equiv19^{7}\equiv7 $
Ora, consideriamo le quarte potenze modulo 13 :
$ 0^4\equiv0 $
$ 1^4\equiv5^4\equiv8^4\equiv12^4\equiv1 $
$ 2^4\equiv3^4\equiv10^4\equiv11^4\equiv3 $
$ 4^4\equiv6^4\equiv7^4\equiv9^4\equiv9 $
Infine, consideriamo le terze potenze, sempre modulo 13 :
$ 0^3\equiv0 $
$ 1^3\equiv3^3\equiv9^3\equiv 1 $
$ 2^3\equiv5^3\equiv6^3\equiv8 $
$ 4^3\equiv10^3\equiv 12^3\equiv12 $
$ 7^3\equiv8^3\equiv11^3\equiv5 $
Quindi ora ci basta provare a fare tutte le somme possibili tra una potenza quarta e una potenza terza modulo 13 e sperare che non faccia mai 7 (modulo 13) :
$ \left\{\begin{array}{c}0\\1\\3\\9\end{array}\right.+\left\{\begin{array}{c}0\\1\\8\\12\\5\end{array}\right. $
Come infatti accade.
In conclusione, abbiamo mostrato che l'equazione scritta non può avere soluzioni, altrimenti si avrebbe un assurdo mod 13.
----
Due parole su come possa venire in mente di affrontare la cosa mod 13 :
1) se c'è una soluzione in interi positivi, è enorme.
2) non ci sono infinite soluzioni, quindi è probabile che, se ci sono soluzioni, bisogna calcolarsele a mano una per una
==> cerchiamo di dimostrare che non ha soluzioni
3) passare l'equazione modulo m è un modo abbastanza usato per dimostrare che non ha soluzioni (se non le può avere modulo m, non le può avere neanche negli interi... ATTENZIONE : non vale il viceversa, però)
4) vale la seguente cosa : dato un numero primo $ p $, se $ k|p-1 $, allora le potenze k-esime non nulle mod p sono (p-1)/k (i quadrati mod p sono (p-1)/2, i cubi non nulli mod 13 sono 12/3=4, le potenze quinte non nulle mod 11 sono 2,...)
5) abbiamo potenze 3e e 4e ... 3*4=12 e 12+1=13 è un primo, quindi mod 13 avrò "poche possibilità" per m^3 e n^4, quindi posso sperare di trovarci un assurdo : se ho pochi valori che possono essere assunti da n^4 e m^3, ho meno modi di combinarli, quindi è più facile che mi venga impossibile ottenere la somma voluta (ovvero il resto di 19^19 mod 13).
Allora ... riscriviamo tutto modulo 13 ...
$ 19\equiv 6\ (\bmod 13) $ e le sue potenze fanno così :
$ 19^0\equiv 1\quad 19^1\equiv 6\quad 19^2\equiv10\quad19^3\equiv8\quad19^4\equiv9\quad19^5\equiv2\quad19^6\equiv-1 $
quindi $ 19^{19}\equiv19^{7}\equiv7 $
Ora, consideriamo le quarte potenze modulo 13 :
$ 0^4\equiv0 $
$ 1^4\equiv5^4\equiv8^4\equiv12^4\equiv1 $
$ 2^4\equiv3^4\equiv10^4\equiv11^4\equiv3 $
$ 4^4\equiv6^4\equiv7^4\equiv9^4\equiv9 $
Infine, consideriamo le terze potenze, sempre modulo 13 :
$ 0^3\equiv0 $
$ 1^3\equiv3^3\equiv9^3\equiv 1 $
$ 2^3\equiv5^3\equiv6^3\equiv8 $
$ 4^3\equiv10^3\equiv 12^3\equiv12 $
$ 7^3\equiv8^3\equiv11^3\equiv5 $
Quindi ora ci basta provare a fare tutte le somme possibili tra una potenza quarta e una potenza terza modulo 13 e sperare che non faccia mai 7 (modulo 13) :
$ \left\{\begin{array}{c}0\\1\\3\\9\end{array}\right.+\left\{\begin{array}{c}0\\1\\8\\12\\5\end{array}\right. $
Come infatti accade.
In conclusione, abbiamo mostrato che l'equazione scritta non può avere soluzioni, altrimenti si avrebbe un assurdo mod 13.
----
Due parole su come possa venire in mente di affrontare la cosa mod 13 :
1) se c'è una soluzione in interi positivi, è enorme.
2) non ci sono infinite soluzioni, quindi è probabile che, se ci sono soluzioni, bisogna calcolarsele a mano una per una
==> cerchiamo di dimostrare che non ha soluzioni
3) passare l'equazione modulo m è un modo abbastanza usato per dimostrare che non ha soluzioni (se non le può avere modulo m, non le può avere neanche negli interi... ATTENZIONE : non vale il viceversa, però)
4) vale la seguente cosa : dato un numero primo $ p $, se $ k|p-1 $, allora le potenze k-esime non nulle mod p sono (p-1)/k (i quadrati mod p sono (p-1)/2, i cubi non nulli mod 13 sono 12/3=4, le potenze quinte non nulle mod 11 sono 2,...)
5) abbiamo potenze 3e e 4e ... 3*4=12 e 12+1=13 è un primo, quindi mod 13 avrò "poche possibilità" per m^3 e n^4, quindi posso sperare di trovarci un assurdo : se ho pochi valori che possono essere assunti da n^4 e m^3, ho meno modi di combinarli, quindi è più facile che mi venga impossibile ottenere la somma voluta (ovvero il resto di 19^19 mod 13).
Grazie.
Riscrivo la parte finale in LaTex in modo che sia più chiaro come approcciare un problemino del genere.
Due parole su come possa venire in mente di affrontare la cosa mod $ 13 $ :
$ 1) $ se c'è una soluzione in interi positivi, è enorme.
$ 2) $ non ci sono infinite soluzioni, quindi è probabile che, se ci sono soluzioni, bisogna calcolarsele a mano una per una $ \rightarrow $ cerchiamo di dimostrare che non ha soluzioni.
$ 3) $ passare all'equazione modulo $ m $ è un modo abbastanza usato per dimostrare che non ha soluzioni (se non le può avere modulo $ m $, non le può avere neanche negli interi... ATTENZIONE : non vale il viceversa, però).
$ 4) $ vale la seguente cosa :
dato un numero primo $ p $, se $ k | p-1 $, allora le potenze $ k $-esime non nulle mod $ p $ sono $ (p-1)/k $ (i quadrati mod $ p $ sono $ (p-1)/2 $, i cubi non nulli sono $ (p-1)/3 $, per cui i cubi non nulli mod $ 13 $ sono $ (13-1)/3 = 4 $, le potenze quinte non nulle mod $ 11 $ sono $ (11-1)/5 = 2 $,...).
$ 5) $ abbiamo potenze terze e quarte perchè $ 3 \cdot 4=12 $ e $ 12+1=13 \in \mathbb{P} $ è un primo, quindi mod $ 13 $ avrò poche possibilità per $ m^3 $ e $ n^4 $, quindi posso sperare di trovarci un assurdo : se ho pochi valori che possono essere assunti da $ n^4 $ e $ m^3 $, ho meno modi di combinarli, quindi è più facile che mi venga impossibile ottenere la somma voluta (ovvero il resto di $ 19^{19} $ mod $ 13 $).
Riscrivo la parte finale in LaTex in modo che sia più chiaro come approcciare un problemino del genere.
Due parole su come possa venire in mente di affrontare la cosa mod $ 13 $ :
$ 1) $ se c'è una soluzione in interi positivi, è enorme.
$ 2) $ non ci sono infinite soluzioni, quindi è probabile che, se ci sono soluzioni, bisogna calcolarsele a mano una per una $ \rightarrow $ cerchiamo di dimostrare che non ha soluzioni.
$ 3) $ passare all'equazione modulo $ m $ è un modo abbastanza usato per dimostrare che non ha soluzioni (se non le può avere modulo $ m $, non le può avere neanche negli interi... ATTENZIONE : non vale il viceversa, però).
$ 4) $ vale la seguente cosa :
dato un numero primo $ p $, se $ k | p-1 $, allora le potenze $ k $-esime non nulle mod $ p $ sono $ (p-1)/k $ (i quadrati mod $ p $ sono $ (p-1)/2 $, i cubi non nulli sono $ (p-1)/3 $, per cui i cubi non nulli mod $ 13 $ sono $ (13-1)/3 = 4 $, le potenze quinte non nulle mod $ 11 $ sono $ (11-1)/5 = 2 $,...).
$ 5) $ abbiamo potenze terze e quarte perchè $ 3 \cdot 4=12 $ e $ 12+1=13 \in \mathbb{P} $ è un primo, quindi mod $ 13 $ avrò poche possibilità per $ m^3 $ e $ n^4 $, quindi posso sperare di trovarci un assurdo : se ho pochi valori che possono essere assunti da $ n^4 $ e $ m^3 $, ho meno modi di combinarli, quindi è più facile che mi venga impossibile ottenere la somma voluta (ovvero il resto di $ 19^{19} $ mod $ 13 $).
Considerate la vostra semenza: fatte non foste a viver come bruti, ma per seguir virtute e canoscenza
La dimostrazione è chiara e perfetta.
Anchio avevo (ovviamente!) pensato di cercare un assurdo tra le congruenze, solo che i calcoloni dei moduli già maggiori di 7 mi avevano scoraggiato.
1 sola domanda:
I conti dei residui delle potenze terze e quarte modulo 13 si fanno a mano?
Cioè devo munirmi di tanta pazienza e far tutti i residui e le loro potenze fin quando non ne incontro 4 e 3 diversi(solo 4 e solo 3 rispettivamente per potenza terza e quarta in virtù del punto $ (4) $ della parte finale del tuo post)
???
Grazie, Bye
Anchio avevo (ovviamente!) pensato di cercare un assurdo tra le congruenze, solo che i calcoloni dei moduli già maggiori di 7 mi avevano scoraggiato.
1 sola domanda:
I conti dei residui delle potenze terze e quarte modulo 13 si fanno a mano?
Cioè devo munirmi di tanta pazienza e far tutti i residui e le loro potenze fin quando non ne incontro 4 e 3 diversi(solo 4 e solo 3 rispettivamente per potenza terza e quarta in virtù del punto $ (4) $ della parte finale del tuo post)
??? Grazie, Bye
Considerate la vostra semenza: fatte non foste a viver come bruti, ma per seguir virtute e canoscenza
Uhm, forse stiamo uscendo un po' off topic, ma tanto ...
Allora, fondamentalmente sì, devi farli a mano, o comunque, se poi devi scrivere una soluzione, è meglio scrivere esplicitamente quanto fa $ n^k $ per tutti gli n tra 0 e m-1 (se lo fai modulo m).
Però, se stai solo facendo una prova per vedere se quel particolare modulo funziona, ci possono essere due o tre trucchi, tra cui :
1) $ n^{2k}\equiv (-n)^{2k} \quad (\bmod m) $ e quindi ti basta calcolare le potenze pari su metà delle classi di resto, poi si ripetono all'inverso (ad es, modulo 13, elevando al quadrato ottieni
0--->0
1--->1
2--->4
3--->9
4--->3
5--->12
6--->10 ($ 6\equiv(13-1)/2\quad (\bmod 13) $)
7--->10 ($ 7\equiv-(13-1)/2\quad (\bmod 13) $)
8--->12
9--->3
10-->9
11-->4
12-->1
13-->0
Quindi devi provare solo i primi (p-1)/2 (se il modulo è un primo p) e in quelli trovi di sicuro tutti i residui quadratici.
2) per le potenze dispari, invece si ha l'ovvio contrario : $ n^{2k+1}\equiv - (-n)^{2k+1}\quad (\bmod m) $ e quindi, arrivato a metà, la sequenza si ripeterà palindromicamente come quella dei quadrati, solo con il segno cambiato.
Quindi ti basta fare i cubi di metà degli elementi e in questo modo troverai metà o metà più uno dei residui cubici, ma saprai che i mancanti si ottengono da quelli che hai già cambiando di segno.
3) se il modulo è un primo p, è noto (ma non facile da dimostrare) che -1 è un quadrato se e solo se $ p=4k+1 $ e quindi ad esempio modulo 13 -1 è un quadrato.
Poi ci sono un po' di cose sulle soluzioni di $ x^k\equiv y^k \quad (\bmod m) $ che permetterebbero di dire quali sono i numeri che hanno potenze congruenti, ma diventano faccende un po' complicate per essere di qualche utilità in cose elementari.
Allora, fondamentalmente sì, devi farli a mano, o comunque, se poi devi scrivere una soluzione, è meglio scrivere esplicitamente quanto fa $ n^k $ per tutti gli n tra 0 e m-1 (se lo fai modulo m).
Però, se stai solo facendo una prova per vedere se quel particolare modulo funziona, ci possono essere due o tre trucchi, tra cui :
1) $ n^{2k}\equiv (-n)^{2k} \quad (\bmod m) $ e quindi ti basta calcolare le potenze pari su metà delle classi di resto, poi si ripetono all'inverso (ad es, modulo 13, elevando al quadrato ottieni
0--->0
1--->1
2--->4
3--->9
4--->3
5--->12
6--->10 ($ 6\equiv(13-1)/2\quad (\bmod 13) $)
7--->10 ($ 7\equiv-(13-1)/2\quad (\bmod 13) $)
8--->12
9--->3
10-->9
11-->4
12-->1
13-->0
Quindi devi provare solo i primi (p-1)/2 (se il modulo è un primo p) e in quelli trovi di sicuro tutti i residui quadratici.
2) per le potenze dispari, invece si ha l'ovvio contrario : $ n^{2k+1}\equiv - (-n)^{2k+1}\quad (\bmod m) $ e quindi, arrivato a metà, la sequenza si ripeterà palindromicamente come quella dei quadrati, solo con il segno cambiato.
Quindi ti basta fare i cubi di metà degli elementi e in questo modo troverai metà o metà più uno dei residui cubici, ma saprai che i mancanti si ottengono da quelli che hai già cambiando di segno.
3) se il modulo è un primo p, è noto (ma non facile da dimostrare) che -1 è un quadrato se e solo se $ p=4k+1 $ e quindi ad esempio modulo 13 -1 è un quadrato.
Poi ci sono un po' di cose sulle soluzioni di $ x^k\equiv y^k \quad (\bmod m) $ che permetterebbero di dire quali sono i numeri che hanno potenze congruenti, ma diventano faccende un po' complicate per essere di qualche utilità in cose elementari.
Beh, c'è anche un altro trucco utile.
Eiste un teoremino, di cui in questi giorni sono diventato sponsor [click!], che funziona per i moduli primi, che dice che esiste almeno (in verità ne esistono tante...) una classe mod p speciale, col nome esotico di elemento primitivo le cui potenze generano tutti gli elementi non nulli mod p.
Per calcolare le potenze generiche, basta scrivere tutto in termini di questo elemento speciale.
Così non si capisce nulla. Vi svolgo i conti mod. 13.
Dunque, cerchiamo un numerillo che elevato alla 12 fa 1, ma non lo fa per nessun numero più piccolo di 12.
Per moduli piccoli si fa bene a calcolare le potenze di 2 a mano [raddoppiare mod p non è difficile...]
$ 2^0=1, 2^1=2, 2^2=4, 2^3=8=-5 $
$ 2^4=-10=3, 2^5=6, 2^6=12=-1 $
Da qui in poi, è anche più facile che raddoppiare, perché la sequenza si ripete e cambia di segno:
$ 2^7=2^6 \cdot 2^1=-1 \cdot 2 = -2, 2^8=2^6 \cdot 2^2=-1 \cdot 4 = -4, \dots $
La sequenza completa è perciò:
$ 2^7=-2, 2^8=-4, 2^9=5, 2^{10}=-3, 2^{11}=-6, 2^{12}=1 $
Oh, bene. Abbiamo avuto cu..fortuna, e 2 è risultato essere l'elemento primitivo. Se per caso nollo fosse stato, pigliavo un numero [piccolo!!, per far bene i conti], che non è una potenza di due e ripetevo il giochino. Se 2 va male, -2 o 3 molto spesso risolvono il problema...
Benone. Significa che ogni numero diverso da 0 (mod 13) si può scrivere come "2 alla qualcosa" mod 13. A questo punto, come faccio le quarte potenze? Basta moltiplicare per 4 gli esponenti. Dato che le potenze di 2 si ripetono con periodo 12, basta vedere gli esponenti mod.12. Le quarte potenze sono perciò:
$ 2^0=1, 2^4=3, 2^8=-4 $. Queste sono le potenze di numeri non nulli. Ricordatevi perciò di aggiungere $ 0^4=0 $.
Inoltre, sapete fare anche le "radici quarte mod 13": $ x^4=3 $. Scrivete $ x=2^e $ per un opportuno esponente e. Allora $ x^4=2^{4e}=?=3=2^4 $. Cioè [ricordate che gli esponenti di 2 sono definiti mod. 12]:
$ 4e=4 \pmod{12} \iff e=1 \pmod 3 $, il che dà: $ 2^1=2, 2^4=3, 2^7=-2, 2^{10}=-3 $.
Eiste un teoremino, di cui in questi giorni sono diventato sponsor [click!], che funziona per i moduli primi, che dice che esiste almeno (in verità ne esistono tante...) una classe mod p speciale, col nome esotico di elemento primitivo le cui potenze generano tutti gli elementi non nulli mod p.
Per calcolare le potenze generiche, basta scrivere tutto in termini di questo elemento speciale.
Così non si capisce nulla. Vi svolgo i conti mod. 13.
Dunque, cerchiamo un numerillo che elevato alla 12 fa 1, ma non lo fa per nessun numero più piccolo di 12.
Per moduli piccoli si fa bene a calcolare le potenze di 2 a mano [raddoppiare mod p non è difficile...]
$ 2^0=1, 2^1=2, 2^2=4, 2^3=8=-5 $
$ 2^4=-10=3, 2^5=6, 2^6=12=-1 $
Da qui in poi, è anche più facile che raddoppiare, perché la sequenza si ripete e cambia di segno:
$ 2^7=2^6 \cdot 2^1=-1 \cdot 2 = -2, 2^8=2^6 \cdot 2^2=-1 \cdot 4 = -4, \dots $
La sequenza completa è perciò:
$ 2^7=-2, 2^8=-4, 2^9=5, 2^{10}=-3, 2^{11}=-6, 2^{12}=1 $
Oh, bene. Abbiamo avuto cu..fortuna, e 2 è risultato essere l'elemento primitivo. Se per caso nollo fosse stato, pigliavo un numero [piccolo!!, per far bene i conti], che non è una potenza di due e ripetevo il giochino. Se 2 va male, -2 o 3 molto spesso risolvono il problema...
Benone. Significa che ogni numero diverso da 0 (mod 13) si può scrivere come "2 alla qualcosa" mod 13. A questo punto, come faccio le quarte potenze? Basta moltiplicare per 4 gli esponenti. Dato che le potenze di 2 si ripetono con periodo 12, basta vedere gli esponenti mod.12. Le quarte potenze sono perciò:
$ 2^0=1, 2^4=3, 2^8=-4 $. Queste sono le potenze di numeri non nulli. Ricordatevi perciò di aggiungere $ 0^4=0 $.
Inoltre, sapete fare anche le "radici quarte mod 13": $ x^4=3 $. Scrivete $ x=2^e $ per un opportuno esponente e. Allora $ x^4=2^{4e}=?=3=2^4 $. Cioè [ricordate che gli esponenti di 2 sono definiti mod. 12]:
$ 4e=4 \pmod{12} \iff e=1 \pmod 3 $, il che dà: $ 2^1=2, 2^4=3, 2^7=-2, 2^{10}=-3 $.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."