Vecchia semifinale canadese

[nuoveolimpiadi1999]

Trovare tutti gli interi che soddisfano 2x^6+y^7=11

[darkcrystal]

Ma fammi capire, l'hai postato per sapere come si fa o perché ti è piaciuto e vuoi condividerlo? Perché onestamente nel secondo caso hai dei gusti strani
Nel primo caso, invece, la risposta è

Testo nascosto:

modulo 43.

[Nadal21]

Ma fammi capire, l'hai postato per sapere come si fa o perché ti è piaciuto e vuoi condividerlo? Perché onestamente nel secondo caso hai dei gusti strani
Nel primo caso, invece, la risposta è

Testo nascosto:

modulo 43.

Ok così si trova che l'equazione non ha soluzione negli interi.
Ma il mio problema è: come arrivo a provare modulo $43$ ?
Per tentativi, o c'è un metodo per cui dovrei capire cosa devo provare?

[darkcrystal]

Per me il ragionamento per arrivare a provare 43 è all'incirca il seguente:
1) se per caso ci sono soluzioni modulo $p^n$ per ogni $p$ ed $n$, non ho veramente idea di cosa fare con questa equazione. Quindi dai, ci sarà un modulo che fa funzionare le cose
2) [tentativo a vuoto] proviamo modulo le solite cose piccole, 2,3, e 7 visto che c'è in un esponente. Potenze di 2? Niente da fare.
3) Ok, cerchiamo di essere un po' più furbi. Diciamo che lavoriamo modulo $p$. Se per caso $7 \nmid p-1$, allora $y^7$ rappresenta tutti i numeri modulo $p$, o in altri termini per ogni $n \in \mathbb{Z}$ c'è $y \in \mathbb{Z}$ tale che $n \equiv y^7 \pmod{p}$ (fatto che dovrebbe essere noto, se non lo è dimostralo! E se non ci riesci chiedi ). Ma allora, se $7 \nmid p-1$, sicuramente ci sono soluzioni modulo $p$: prendo semplicemente $x=0$ e poi risolvo $y^7 \equiv 11 \pmod{p}$, che abbiamo appena detto avere soluzioni. Quindi serve provare solo i primi per i quali $7 \mid p-1$, ovvero i primi $p \equiv 1 \pmod {14}$. I primi casi da tentare sarebbero quindi 29 e 43
4) In realtà ho provato 43 prima di 29 (che per inciso non funziona), per il motivo seguente. Prima abbiamo visto che - imponendo $x=0$ - ci sono certamente soluzioni non appena $7 \nmid p-1$. Ora vediamo cosa succede con $y=0$: ci chiediamo se $2x^6 \equiv 11 \pmod{p}$ abbia una soluzione o meno. Il punto è che se 3 non divide $p-1$, allora l'equazione $x^6 \equiv n \pmod{p}$ è risolubile se e solo se lo è l'equazione $x^2 \equiv n \pmod{p}$ (di nuovo, dimostrare!). Quindi, se per caso $3 \nmid p-1$, c'è essenzialmente "il 50% di probabilità" che l'equazione $x^6 \equiv 2^{-1} \cdot 11 \pmod{p}$ abbia una soluzione, il che non è il massimo ("il 50% di probabilità" ovviamente non ha molto senso, una cosa o è residuo quadratico o non lo è... ma quello che voglio dire è che circa metà dei numeri sono residui quadratici modulo $p$ per un primo $p$ fissato, e io non ho idea di cosa sia $2^{-1} \cdot 11 \pmod{p}$, quindi posso pensare - in prima approssimazione - che sia "un numero a caso"). Invece, se $p \equiv 1 \pmod{3}$ (e $p \neq 2$), allora c'è solo "circa 1/6 di probabilità" che l'equazione $x^6 \equiv 2^{-1}\cdot 11 \pmod p$ sia risolubile (perché i "residui sestici" modulo $p$ sono $\frac{p-1}{6}$). Quindi meglio provare $p \equiv 1 \pmod 3$! Morale, è *necessario* prendere $p \equiv 1 \pmod {14}$, e sembra *conveniente* prendere $p \equiv 1 \pmod{3}$. Quindi $p=43$ è veramente il primo tentativo da fare.

Va meglio ora?

[Vinci]

Scusate, ma come fate a trovare velocemente tutte le possibili classi di resto di $x^6$ e $y^7$ $\pmod{43}$?

[darkcrystal]

Sigh, speravo di poter evitare, ma... here we go. Premessa: questo post è scritto di getto, e alla fine contiene dei commenti dei tipo "Ah, beh, ma in effetti sono un idiota, questi passaggi potevano essere evitati". Mentre lo leggi, cerca di vedere se noti dove si potrebbero accelerare i conti...

Cominciamo a calcolare potenze settime, per esempio. Abbiamo $1^7 \equiv 1$ e $2^7 \equiv 128 \equiv -1 \pmod{43}$. In particolare, si ha $4^7 \equiv 1 \pmod{43}$. E qui c'è una prima osservazione chiave per accelerare i conti: per ogni intero $a$ si ha $(4a)^7 \equiv 4^7 a^7 \equiv a^7 \pmod{43}$. Dunque, per esempio, i seguenti numeri hanno tutti la stessa potenza settima modulo 43: $1, 4, 16, 4^3 \equiv 21, 4^4 \equiv -2, 4^5 \equiv -8, 4^6 \equiv 11$ (in particolare, elevati alla settima fanno tutti 1).
D'altro canto, siccome $(-1)^7 = -1$, abbiamo che $-1, -4, -16, -21, 2, 8, -11$, quando elevati alla settima, danno $-1$.
E ora andiamo avanti: nelle due liste precedenti non compare 3, quindi calcoliamo $3^7 \equiv -6$. Chiaramente $-3$ alla settima darà $6$, e abbiamo già trovato 4 residui settimi ($\pm 1, \pm 6$). Ora fare $4^7$ non serve a niente (sappiamo già che fa 1), e $5^7$ non ci aiuta perché $5 \equiv 3 \cdot 4^2 \pmod{43}$. Anche $6^7 \equiv (-3)^{7 \cdot 7} \equiv (-3)^{49-\varphi(43)} = (-3)^7 \equiv 6$ non ci serve, e quindi proviamo $7^7 \equiv 7 \pmod {43}$. Questo è un residuo che non avevamo ancora visto, e chiaramente si ha anche $(-7)^7 \equiv -7 \pmod{43}$. Quindi $\{\pm 1, \pm 3, \pm 7\}$ sono residui settimi. D'altro canto, il numero di residui settimi non-zero è $\frac{43-1}{7}=6$, quindi li abbiamo trovati tutti.

Ok, questo non era troppo male, ma un pochino di tempo c'è voluto. Ora con le potenze seste usiamo un'altra idea e facciamo ancora meglio!
Certamente abbiamo $1^6 = 1$, $2^6 \equiv 4^3 \equiv 21$. Fermiamoci un istante a pensare: se $n$ è una potenza sesta, diciamo $n \equiv a^6 \pmod{43}$, chiaramente anche $n^2$, $n^3$ eccetera sono potenze seste (sono le potenze di $a^2, a^3,...$)! Allora forse posso essere più efficiente e calcolare $21^2, 21^3, ...$. Vediamo cosa succede. $21^2 \equiv 2^{12} \equiv 4^6 \equiv 11$, e il conto è gratis perché l'abbiamo già fatto prima. Ora $21^3 \equiv 2^{18} \equiv 4^9 \equiv 4^2 \equiv 16 \pmod{43}$, e questo è un nuovo residuo sesto! Ora $21^4 \equiv 2^{24} \equiv 4^{12} \equiv -8 \equiv 35 \pmod{43}$, anche questo è nuovo. E ancora $21^5 \equiv 4^{15} \equiv 4^7 \cdot 4^7 \cdot 4 \equiv 4 \pmod{43}$... yay! Ed infine $21^6 \equiv 21 \cdot 4 \equiv 84 \equiv -2 \pmod{43}$, che è ancora diverso. Ora mi fermo di nuovo un attimo a pensare: abbiamo già trovato $\{1,21,11,16,35,4,41\}$, che sono 7 classi di resto, e sappiamo che i residui sesti sono $\frac{43-1}{6}=7$, quindi abbiamo finito. E non mi puoi dire che sia stato un conto difficile: alla peggio abbiamo dovuto fare $84 \bmod 43$!

Ma in realtà è ancora meglio di quanto non sembri: sapevamo a priori che fare le potenze di $21$ avrebbe funzionato! Infatti, qual è l'ordine moltiplicativo di 21 modulo 43? Beh, sappiamo che $21=2^6$, quindi $21^7 \equiv 2^{42}\equiv 1 \pmod{43}$. Dunque l'ordine moltiplicativo di 21 divide 7, ma certamente non è 1, quindi è necessariamente proprio 7. Il che vuol dire che $21^1, 21^2, 21^3, 21^4, 21^5, 21^6, 21^7=1$ sono tutti diversi modulo 43. Ma siccome sono anche tutte potenze seste - l'abbiamo già visto - sono tutti e soli i residui sesti.

Ora i commenti del tipo "ma in realtà sono scemo". Nota che per trovare le potenze settime avremmo potuto essere più efficienti e - una volta trovato che $6$ è una potenza settima - avremmo potuto finire molto più velocemente calcolando $6^2 = 36 \equiv -7$. Ma a volte anche l'altra idea può essere utile!
Inoltre, se uno vuole ridurre veramente al minimo il numero dei conti da fare (e da scrivere in una gara...), una volta scoperto che 21 è una potenza sesta, con un minimo di ragionamento - ma bisognava fermarsi a pensare un po' di più - si sarebbe potuto osservare (l'avevate notato, miei attenti lettori?) che in effetti le potenze seste non sono altro che le potenze di 4, che avevamo già calcolato!

p.s. Naturalmente la risposta vera alla tua domanda è "con un computer" . Ma fare il conto come qui sopra prende solo una manciata di minuti, soprattutto se lo fai con carta e penna e non scrivendo direttamente in LaTeX ...

[Gerald Lambeau]

Riprendo quello che ho scritto in un altro topic per generalizzare un po' i ragionamenti fatti da darkcrystal sul perché scegliere $43$, poiché conoscendo quello che sto per scrivere diventa palese che è la prima cosa che uno prova.

Se si ha una diofantea con tutti gli esponenti noti, si prenda il loro multiplo comune più piccolo (non necessariamente il minimo comune multiplo!) tale che esso incrementato di $1$ sia primo. Quel primo è quello il cui modulo dobbiamo guardare.
Nel nostro caso siamo fortunati, infatti basta il minimo comune multiplo: $6 \cdot 7+1=43$ (in generale preferiamo guardare solo quello, altrimenti si rischia di beccare un primo troppo grande affinché il trucco funzioni bene).

Spieghiamo ora perché il trucco funziona così bene con primi relativamente piccoli (=vicini al minimo comune multiplo degli esponenti):
modulo un primo $p$ esistono $\displaystyle \frac{p-1}{MCD(k, p-1)}+1$ residui $k$-adici modulo $p$; se noi sappiamo che $k \mid p-1$, siamo certi che quel numero sarà minore di $p$. Ancora meglio se $p-1$ è il minimo comune multiplo degli esponenti, perché sì minimizza il numero di casi possibili.
Avendo pochi casi, se siamo fortunati la diofantea non potrà essere rispettata da nessuna combinazione di moduli.

[Vinci]

Grazie mille, mi sarà un utilissimo esempio per il futuro

[Nadal21]

Grazie, grazie, grazie. Molto utile.

[Vinci]

, il numero di residui settimi non-zero è $\frac{43-1}{7}=6$, quindi li abbiamo trovati tutti.

Scusate, ma non ho capito il perchè di questo

[Talete]

, il numero di residui settimi non-zero è $\frac{43-1}{7}=6$, quindi li abbiamo trovati tutti.

Scusate, ma non ho capito il perchè di questo

Per quello che ha detto Gerald Lambeau prima: dato un primo $p$ ed un intero $k$, il numero di residui $k$-esimi non nulli modulo $p$ è
\[\frac{p-1}{\mathrm{mcd}(k,p-1)}.\]

[Vinci]

E come si dimostra?

[Gerald Lambeau]

Dati due resti diversi modulo $p$, se $g$ è un generatore scriviamoceli come $g^a$ e $g^b$, per opportuni $a \not=b$. L'uso dei generatori ci fa escludere lo $0$ per ora.
Vogliamo sapere quando $(g^a)^k \equiv (g^b)^k \pmod{p} \Rightarrow g^{ak} \equiv g^{bk} \pmod{p}$. Essendo $g$ un generatore modulo $p$, l'ultima uguaglianza vale se e solo se $ak \equiv bk \pmod{p-1}$.
Questo vale se e solo se $\displaystyle a \equiv b \pmod{\frac{p-1}{MCD(k, p-1)}}$. Questo ti dice che ce n'è al più $\displaystyle \frac{p-1}{MCD(k, p-1)}$ diversi, ma siccome quel numero è minore o uguale di $p-1$, allora ne abbiamo trovati proprio quel numero lì (un generatore ha esattamente $p-1$ potenze diverse, alla peggio, cioè quando $MCD(k, p-1)=1$, le dobbiamo usare tutte).
Dobbiamo però riaggiungere lo $0$, quindi $+1$.