Tre numeri dal 2017

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
razorbeard
Messaggi: 123
Iscritto il: 20 apr 2011, 16:28

Tre numeri dal 2017

Messaggio da razorbeard »

Quante sono le terne di interi $a,b,c \in {0,...,70}$ tali che $a^2+b^2-2c^2$ sia multiplo di 71?
E' un buon giorno... per morire
soleka_miskutino
Messaggi: 3
Iscritto il: 23 ago 2020, 20:04

Re: Tre numeri dal 2017

Messaggio da soleka_miskutino »

Il tutto si dovrebbe ridurre a trovare le terne di soluzioni in $Z_{71} $. 2 è congruo a $12^2$ modulo 71 quindi con un'opportuna sostituzione il problema si riduce a contare le terne pitagoriche in $Z_{71} $. E da qui in avanti per ora non trovo metodi veloci.
kart
Messaggi: 9
Iscritto il: 31 mar 2020, 09:05

Re: Tre numeri dal 2017

Messaggio da kart »

Ci provo
Testo nascosto:
Dobbiamo risolvere $a^2+b^2-2c^2 \equiv 0 \pmod{71}$. Ci troviamo in $\mathbb{F}_{71}$, quindi esiste almeno un generatore $g$ e vale la legge di annullamento del prodotto.
Notiamo che $2 \equiv 12^2 \pmod{71}$, quindi abbiamo che
\[ a^2+b^2 \equiv (12c)^2 \pmod{71} \;\;\implies\;\; a^2 \equiv (12c-b)(12c+b) \pmod{71} \]
Applichiamo ora la sostituzione
\[ \begin{cases} u \equiv 12c+b \pmod{71} \\ v \equiv 12c-b \pmod{71} \end{cases} \implies
\begin{cases} b \equiv 2^{-1}(u-v) \pmod{71} \\ c \equiv 24^{-1}(u+v) \pmod{71} \end{cases} \implies
\begin{cases} b \equiv 36(u-v) \pmod{71} \\ c \equiv 3(u+v) \pmod{71} \end{cases} \]
che è chiaramente biiettiva. Quindi ci siamo ricondotti a contare il numero di terne in $\mathbb{F}_{71}$ che soddisfano
\[ a^2 \equiv uv \pmod{71} \]
  • Se $a \equiv 0 \pmod{71}$ abbiamo che
    \[ uv \equiv 0 \pmod{71} \implies u \equiv 0 \pmod{71} \;\;\lor\;\; v \equiv 0 \pmod{71} \]
    Quindi ci sono $71+71-1=141$ terne.
  • Se $a \not\equiv 0 \pmod{71}$ abbiamo che
    \[ uv \not\equiv 0 \pmod{71} \implies u \not\equiv 0 \pmod{71} \;\;\land\;\; v \not\equiv 0 \pmod{71} \]
    Quindi esiste $g$ generatore tale che $u \equiv g^{t_1} \pmod{71}$ e $v \equiv g^{t_2} \pmod{71}$, con $t_1,t_2 \in \{1,2,\dots,70\}$
    \[ uv \equiv g^{t_1+t_2} \equiv a^2 \pmod{71} \implies t_1+t_2=2k, \text{con $k$ intero} \]
    Contiamo ora le coppie $(t_1,t_2)$ che soddisfano la precedente equazione
    \[ t_1 \;\text{pari} \implies t_2 \;\text{pari} \implies 35\cdot35 \;\text{coppie} \\
    t_1 \;\text{dispari} \implies t_2 \;\text{dispari} \implies 35\cdot35 \;\text{coppie} \]
    per un totale di $2\cdot35\cdot35=2450$ coppie. Notiamo infine che
    \[ a^2 \equiv g^{2k} \pmod{71} \implies (a-g^k)(a+g^k) \equiv 0 \pmod{71} \\ \implies a \equiv g^k \pmod{71} \;\;\lor\;\; a \equiv -g^k \pmod{71} \]
    e inoltre $g^k \not \equiv -g^k \pmod{71}$, infatti se fosse $g^k \equiv -g^k \pmod{71}$, allora si avrebbe $2g^k \equiv 0 \pmod{71} \implies g^k \equiv 0 \pmod{71}$, assurdo poiché $g$ è generatore.
    Quindi se $a \not\equiv 0 \pmod{71}$, abbiamo $2450\cdot2=4900$ terne.

In totale ci sono quindi $4900+141=5041$ terne.
soleka_miskutino
Messaggi: 3
Iscritto il: 23 ago 2020, 20:04

Re: Tre numeri dal 2017

Messaggio da soleka_miskutino »

Risultato corretto. Ho controllato sul PDF delle soluzioni della gara a squadre. Rimane da capire come si potrebbe risolvere solo con i mezzi a disposizione di un olimpionico base ( mi pare che la struttura moltiplicativa in Zn non fa parte del curriculum richiesto a livello di gare a squadre). O scrivo stupidaggini?
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Tre numeri dal 2017

Messaggio da fph »

Kart sta usando i cannoni perché li conosce, ma non serve davvero saperne di generatori per contare le terne $(a,u,v)$ tali che $a^2=uv$ negli interi modulo 71. Per ogni scelta di $a\neq 0$ e $v\neq 0$, esiste uno e un solo $v$ che va bene, e si trova moltiplicando $a^2$ per l'inverso di $u$. Tutto quello che ti serve sapere è l'esistenza (e unicità) degli inversi moltiplicativi, che è ben più facile.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
kart
Messaggi: 9
Iscritto il: 31 mar 2020, 09:05

Re: Tre numeri dal 2017

Messaggio da kart »

Già purtroppo quando si imparano tecniche un po' op si tende ad applicarle a tutto dimenticandosi di fatti molto più semplici ed elementari :oops: , quindi grazie mille fph per averlo fatto notare
Rispondi