164-$ax^p+by^p$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: 164-$ax^p+by^p$

Messaggio da maurizio43 »

Immagino che con questa mia umile domanda provocherò in tutti l' orticaria , causa overdose di scandalo, e che potrete chiedere il rogo per me... ma mi appello al vostro spirito di comprensione e tolleranza.
Mi potete informare del significato del termine "wlog" ?
Scusate il disturbo, immagino che sia concetto banalissimo, ma quando ho cercato informazioni in proposito non avuto risultati .
(P.S.: Siccome ho lo stesso problema anche per altri termini e simboli, potete indicarmi una fonte a cui abbeverare la mia ignorante sete di informazioni ? )
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 164-$ax^p+by^p$

Messaggio da jordan »

Tranquillo, wlog sta per without loss of generality http://en.wikipedia.org/wiki/Without_loss_of_generality :wink:
Quali sono gli altri simboli con cui ci sono problemi?
The only goal of science is the honor of the human spirit.
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: 164-$ax^p+by^p$

Messaggio da maurizio43 »

Sei molto gentile, grazie. Tanto mio imbarazzo, e poi... si trattava del caro, vecchio "Senza ledere la generalità", che però nessuno aveva mai contratto in "Sllg"... :)
Domandine :
- Che significa $gpf$ ? - Che significa $gcd$ ? - Che cavolo di funzione è la $ \ phi $ ?
Visto che ti ritrovi dotato di una buona dose di cristiana pazienza, non te la voglio esaurire tutta subito , e per ora mi fermo qui .

P.S.:
Ho notato che vi muovete con molta disinvoltura in ragionamenti sulla rappresentazione dei numeri " modulo 'qualcosa' ",
come se fossero già ampiamente note e scontate certe proprietà su questa 'modularità' , che mi sembrano molto comode,
che una ad una -pensandoci- condivido , ma davanti all' uso alle quali mi fermo per mancanza di confidenza .
Puoi indicarmi un testo in proposito , per imparne l' abc ( e magari anche la d e la e .... )
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: 164-$ax^p+by^p$

Messaggio da Triarii »

gpf dovrebbe stare per greatest prime factor, ossia è la funzione che associa ad un numero n il più grande primo presente nella sua fattorizzazione (tuttavia su questa chiedo conferma perchè non ne sonno troppo sicuro)
gcd sta per greatest common divisor, quindi in italiano è il massimo comun divisore ;)
la funzione $\phi$ è la funzione che associa ad un intero $n$ il numero di numeri ad esso coprimi minori o uguali di $n$. So che mi sono spiegato male, quindi ecco un esempio: $\phi (6)=2$ in quanto fra i numeri minori od uguali a 6, solo 1 e 5 sono coprimi con 6. $\phi (7)=6$ in quanto tutti i numeri più piccoli di 7 sono ad esso coprimi. Probabilmente già lo saprai, ma lo ridico per scrupolo: due numeri $m$, $n$ si dicono coprimi se il loro massimo comun divisore è 1.
"We' Inge!"
LTE4LYF
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 164-$ax^p+by^p$

Messaggio da jordan »

maurizio43 ha scritto:Domandine :
- Che significa $gpf$ ? - Che significa $gcd$ ? - Che cavolo di funzione è la $ \ phi $ ?
In ordine: $\text{gpf}$ è il piu' grande fattore primo (greatest prime factor) dell'argomento, che dovrà essere un intero con modulo maggiore di 1; $\text{gcd}$ è il greatest common divisor, il massimo comun divisore; riguardo la $\phi$, non ne ho trovate in questo thread, ma immagino ti riferisca alla $\phi$ di Eulero, cioè $\phi(n)$ è il numero di interi positivi, minori o uguali a $n$ e coprimi con esso (quindi per esempio $\phi(1)=1$, $\phi(8)=4$ e $\phi(p)=p-1$ per ogni primo $p$)
maurizio43 ha scritto:Visto che ti ritrovi dotato di una buona dose di cristiana pazienza, non te la voglio esaurire tutta subito , e per ora mi fermo qui .
Tranquillo, il forum è fatto apposta ;)
maurizio43 ha scritto:Puoi indicarmi un testo in proposito , per imparne l' abc ( e magari anche la d e la e .... )
Molti testi partono teoricamente dall'abc, ma la maggior parte di questi presume già una certa familiarità con questi argomenti (specie le dispense liberamente accessibili); ne ho pero' trovato uno che fa davvero tutto, per arrivare all'aritmentica modulare sarai già a pag.150 (vedi qui); qualcosa del genere molto piu' stringato qui. Se poi ti risultassero troppo facili e/o lenti, passa a questo. Con questi, avrai da fare per almeno qualche mese :D

Edit: battuto sul tempo
The only goal of science is the honor of the human spirit.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 164-$ax^p+by^p$

Messaggio da jordan »

xXStephXx ha scritto:[...]Per ora pongo $k> \alpha$ e ottengo modulo $q^\alpha$ che $q^\alpha | y^p$ e ottengo un'equazione del tipo
$\displaystyle q^\alpha x^p + bq^{\lceil \frac{\alpha}{p} \rceil p}y^p = q^k$ (faccio finta di dimenticare gli altri fattori di $a$ e metto in evidenza solo ciò che mi serve). [...]
Perchè?

Per non contare che $p\lfloor \alpha / p \rfloor - \alpha$ è sempre non positivo..
The only goal of science is the honor of the human spirit.
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: 164-$ax^p+by^p$

Messaggio da maurizio43 »

Per Jordan e Triarii.
-----------------------
Siete entrambi persone di squisita gentilezza.
Ringrazio e ..... Chapeau ! :)
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 164-$ax^p+by^p$

Messaggio da xXStephXx »

jordan ha scritto:
xXStephXx ha scritto:[...]Per ora pongo $k> \alpha$ e ottengo modulo $q^\alpha$ che $q^\alpha | y^p$ e ottengo un'equazione del tipo
$\displaystyle q^\alpha x^p + bq^{\lceil \frac{\alpha}{p} \rceil p}y^p = q^k$ (faccio finta di dimenticare gli altri fattori di $a$ e metto in evidenza solo ciò che mi serve). [...]
Perchè?

Per non contare che $p\lfloor \alpha / p \rfloor - \alpha$ è sempre non positivo..
Era la parte intera superiore (credo). E avevo pure supposto che $p$ non divide $\alpha$. Altrimenti se tutti i fattori primi di $a$ e $b$ avessero solo primi con esponenti divisibili per $p$ potrei ricondurmi al caso di somma di potenze $p-esime$.

Potrei aver preso grossi abbagli xD

Comunque se $q^\alpha$ divide $RHS$ e divide anche $ax^p$ allora deve dividere pure $by^p$. Ora $a$ e $b$ sono coprimi, quindi $q^\alpha | y^p$.
Quindi da $y$ devo tirar fuori un $q$ preso con esponente tanto quanto basta per essere divisibile per $q^\alpha$, ma l'esponente sarà anche un multiplo di $p$ visto che è tirato fuori da una potenza $p-esima$ e dunque credo che sia $\displaystyle q^{\big \lceil \frac{\alpha}{p} \big \rceil p}$
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 164-$ax^p+by^p$

Messaggio da jordan »

xXStephXx ha scritto:Era la parte intera superiore (credo).
Dovrei portarli sempre gli occhiali, sorry :)
xXStephXx ha scritto:Altrimenti se tutti i fattori primi di $a$ e $b$ avessero solo primi con esponenti divisibili per $p$ potrei ricondurmi al caso di somma di potenze $p-esime$.
Perchè scusa, se ne esistessero due di tali $q$? Per esempio se $p=3$, $b=7$ e $a=13^{13} \cdot 17^{17}$?

Ps. Per favore, non usare gli stessi nomi quando cambi le variabili..
Ps2. Grazie maurizio
The only goal of science is the honor of the human spirit.
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 164-$ax^p+by^p$

Messaggio da xXStephXx »

Scusa se non ho cambiato variabili xDDD Un po' di pigrizia :mrgreen: (vabbè spero si capisca uguale quali erano le intenzioni xDD)

In quel caso dovrebbe funzionare indifferentemente sia con $q=17$ e $\alpha=17$ sia con $q=13$ e $\alpha=13$ sia con $q=7$ e $\alpha=1$.
Studiandola nel primo caso ottengo che non posso generare $17^{19}$. Studiandola nel secondo caso non posso generare $13^{14}$. E studiandola nel terzo caso non posso generare $7^2$. (sempre se non ho cannato la dimostrazione xD)

L'idea era questa:
Se $a$ e $b$ non hanno nessun fattore primo, risolvo il caso delle potenze $p-esime$.
Se $a$ e $b$ hanno solo fattori primi con esponenti divisibili per $p$ sono un sottocaso del caso precedente.
Se tra $a$ e $b$ c'è almeno un fattore primo con esponente non divisibile per $p$ chiamo quello $q$ e il suo esponente lo chiamo $\alpha$.
Nella dimostrazione ho supposto wlog che tale fattore appartenga ad $a$.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 164-$ax^p+by^p$

Messaggio da jordan »

Ok per il wlog. Il problema è un altro, mi pare supponi che questo primo $q$ sia unico:

Nel caso di prima, mettiamo $q^{\alpha}=17^{17}$. L'obiettivo è dimostrare allora che
\[ 13^{13}\cdot 17^{17}\cdot x^3+7y^3= 17^k \]
non ha soluzione per almeno un $k>17$. Ora come fai a ricondurre quest'equazione a una del tipo
\[ 17^{17} X^3 + 7\cdot 17^{6\cdot 3} Y^3 = 17^K ?\]

Cioè, quel $13^{13}$ che fine fa?
The only goal of science is the honor of the human spirit.
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: 164-$ax^p+by^p$

Messaggio da maurizio43 »

Per Jordan :
La tua affermazione (a fronte dello sviluppo del cubo di $110c+10d+u$) che " si può 'piu' semplicemente' mostrare che la divisibilita' $100 \mid x^3-50$ non ha soluzione", mostra (ahimè) quanto abissale sia il gap culturale tra noi, specialmente in fatto di matematica modulare ... :)

( Comunque anche lavorare sul cubo del trinomio non era complicato, perchè saltava all'occhio che bisognava ragionare solo sulla somma dei 2 soli termini che potevano non essere multipli di 100 : quello con le unità al cubo e quello col quadrato delle unità moltiplicato per il termine delle decine , da cui era immediata la conclusione ) :wink:
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 164-$ax^p+by^p$

Messaggio da jordan »

Pensaci un attimo: ragionare in termini di "trinomio" o di "aritmetica modulare" è di fatto equivalente. Mi spiego meglio, nel tuo caso la scelta di rappresentare un intero $x$ nella forma
\[ x=100c+10d+u \]
per qualche intero $c,d,u$ con $u,d \in \{0,\ldots,9\}$ e $c$ intero positivo (la storia del possiamo aggiungere migliaia non serve, visto che è sufficiente imporre $c$ positivo) non è casuale: a te servono soltanto le ultime due cifre nella rappresentazione decimale di $x^3$. Una ulteriore semplificazione, hai "spezzato" unità e decine con i valori di $u,d$. Sei d'accordo che è lo stesso considerare un intero nella forma
\[ x=100c+v\]
con $v \in \{0,\ldots,99\}$ e $c$ intero positivo?

Bene, noi siamo interessati alle sole ultime due cifre di una sua potenza $x^n$, che è
\[ x^n=(100c+v)^n=\underbrace{100^nc^n+\binom{n}{n-1}100^{n-1}c^{n-1}v+\ldots+\binom{n}{1}100cv^{n-1}}_{\text{multiplo di }100}+v^n. \]
Questo mostra che le ultime due cifre di $x^n$ sono esattamente le ultime due cifre di $v^n$.

Ora, cos'è $v$? La classe di resto modulo $100$ di $x$. In altre parole, se vogliamo mostrare che nessuno cubo termina per $50$ e' equivalente mostrare che $v^3$ non termina per $50$ per ogni $v \in \{0,1,\ldots,49\}$..

Perchè questo messaggio? Perchè di solito non ti capita di ragionare con moduli comodi come il $100$ :wink:
The only goal of science is the honor of the human spirit.
maurizio43
Messaggi: 181
Iscritto il: 05 lug 2013, 10:27

Re: 164-$ax^p+by^p$

Messaggio da maurizio43 »

Sono d' accordissimo e sono ben conscio che si tratta di fatti equivalenti !
[ E in ambo i casi si tratta di 4 o 5 passaggi logici in tutto]
E' la forma mentis di chi non è abituato a ragionare in termini "modulari" che privilegia gli sviluppi dei cubi ed ha dei limiti ad applicare i meccanismi
delle operazioni "modulo qualcosa.." ; e trova più semplici gli uni e meno semplici gli altri ...
Presumo che questo finirà quando avrò letto i testi che mi hai consigliato :) . E avrò la giusta confidenza per pensare istintivamente in termini di calcolo modulare e utilizzarne disinvoltamente le varie proprietà.
(Così potrò affrontare agevolmente anche casi meno particolari dei multipli di 100 ).
(Col metodo di sviluppare le potenze ,sono d'accordo, ci si impantana molto presto, nei casi generici. Ma qui bastava il caso semplice...).
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 164-$ax^p+by^p$

Messaggio da xXStephXx »

Ehm..... Suvvia ho fatto finta che non ci fossero altri fattori :lol: (però non dovrei aver barato (troppo))
Ok... l'ho scritta in modo osceno xD Provo a riscriverla seriamente LOL

Passo 1: con $ax^2+by^2$ ci sono infiniti numeri che non posso generare.
  • Se almeno uno tra $|a|$ e $|b|$ è maggiore di $2$, suppongo wlog che $|a|>2$. Studiando l'equazione modulo $a$ ottengo $by^2$. I residui di $by^2 \pmod a$ sono al più $\bigg\lceil \frac{|a|}{2} \bigg\rceil$ visto che $by^2 \equiv b(-y)^2 \pmod a$. Di conseguenza non posso generare tutti i numeri con residui diversi da quelli che posso ottenere.
  • Se $|a|$ e $|b|$ sono entrambi minori di $3$ le uniche possibilità (wloggando un po' sui segni e su $a$ e $b$) sono $x^2+y^2$, $x^2-y^2$ limitate modulo $4$ e $2x^2-y^2$, $2x^2+y^2$ limitate modulo $8$.
Passo 2: con $x^p+y^p$ ci sono infiniti numeri che non posso generare.
Infatti non posso generare quelli divisibili per $p$ ma non per $p^2$. Poichè se $x^p+y^p$ è divisibile per $p$, per il PTF lo è anche $x+y$ e applicando LTE si ha che $v_p(x^p+y^p) > 1$.

Passo 3: se $a$ e $b$ hanno solo fattori primi con esponenti multipli di $p$ ci sono infiniti numeri che non posso generare.
In questo caso ottengo numeri della forma $(mx)^p + (ny)^p$ ed è già trattto al Passo 2.

Passo 4: se almeno uno tra $a$ e $b$ ha almeno un fattore primo $q$ con esponente $\alpha$ non multiplo di $p$ ci sono infiniti numeri che non posso generare.

Suppongo wlog che $q^\alpha | a$ ( e se c'è più di un $q$ che rientra in questo caso ne prendo uno qualsiasi ).
Pongo anche $a_1= \frac{a}{q^\alpha}$
  • Dimostro che se $\alpha \equiv -1 \pmod p$ non posso generare $q^{\alpha+2}$
    Se per assurdo lo potessi generare dovrei avere soluzioni all'equazione $q^\alpha a_1 x^p + by^p=q^{\alpha+2}$
    Modulo $q^\alpha$ ottengo che $q^\alpha | y^p$. Dunque necessariamente ho che $y^p = q^{\lceil \frac{\alpha}{p} \rceil p}y_1^p$.
    Ottengo quindi $q^\alpha a_1 x^p + bq^{\lceil \frac{\alpha}{p} \rceil p}y_1^p=q^{\alpha+2}$
    Divido per $q^\alpha$ e ottengo $a_1x^p+bqy_1^p= q^2$.
    (Siccome $\alpha \equiv -1 \pmod p$, allora $q^{\lceil \frac{\alpha}{p} \rceil p-\alpha}=q$).
    Ora modulo $q$ ho che $x^p=q^px_1^p$ e quindi $a_1q^px_1^p + bqy_1^p = q^2$.
    Divido tutto per $q$ e ottengo $a_1q^{p-1}x_1^p + by_1^p = q$
    Sempre modulo $q$ ottengo $y_1^p = q^py_2^p$ e dunque $a_1q^{p-1}x_1^p + bq^py_2^p = q$. Divido per $q$ e ottengo
    $a_1q^{p-2}x_1^p + bq^{p-1}y_2^p = 1$ (ricordo che $p>2$ e il caso $p=2$ l'ho già trattato).
    Ora $LHS$ è divisibile per $q$ mentre $RHS$ no, quindi non ci sono soluzioni.
  • Dimostro che se $\alpha \neq -1 \pmod p$ non posso generare $q^{\alpha+1}$
    In questo caso $\lceil \frac{\alpha}{p} \rceil p - \alpha >1$. (ricordo anche che $\alpha$ non era multiplo di $p$).
    I primi passaggi sono identici a prima e arrivo ad un'equazione del tipo:
    $q^\alpha a_1 x^p + bq^{\lceil \frac{\alpha}{p} \rceil p}y_1^p=q^{\alpha+1}$
    Divido per $q^\alpha$ e ottengo $a_1x^p + bq^{\lceil \frac{\alpha}{p} \rceil p-\alpha}y_1^p = q$.
    Ora modulo $q$ ottengo che $x^p=q^px_1^p$
    Ovvero $a_1q^px_1^p + bq^{\lceil \frac{\alpha}{p} \rceil p-\alpha}y_1^p = q$
    Divido tutto per $q$ e ottengo
    $a_1q^{p-1}x_1^p + bq^{\lceil \frac{\alpha}{p} \rceil p-\alpha-1}y_1^p = 1$
    $LHS$ è divisibile per $q$ poichè $\lceil \frac{\alpha}{p} \rceil p-\alpha-1 > 0$ e $p-1>0$, mentre $RHS$ no. Quindi non ci sono soluzioni
Di conseguenza esiste sempre almeno un $k$ tale che $q^k$ non è generabile, e dunque non lo è manco $q^k+q^M$ con $M$ abbastanza grande, poichè otterrei $RHS \equiv 1 \pmod q$ quando $k$ si annulla come mostrato prima.
Rispondi