Lemma del guadagno di un primo

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?

Moderatore: tutor

Rispondi
Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Lemma del guadagno di un primo

Messaggio da Enigmatico » 01 dic 2015, 17:27

Ciao ragazzi, seguo il consiglio di erFuricksen (scusa se l'ho scritto male...). Su internet non riesco a trovare niente di soddisfacente, perciò chiedo a voi: cosa dice il lemma del guadagno di un primo? In quali casi è utile?

Grazie mille per la disponibilità!!

erFuricksen
Messaggi: 155
Iscritto il: 28 lug 2014, 10:01
Località: Genova

Re: Lemma del guadagno di un primo

Messaggio da erFuricksen » 01 dic 2015, 19:01

Allora, vediamo se posso aiutarti.

Il lemma dice: Siano $a,n>1$ due numeri naturali, allora ${a^n-1} \over {a-1}$ contiene almeno un fattore primo che non è contenuto in $a-1$, a meno che $a=3$ e $n=2$.

Dimostrazione: Possiamo considerare (quasi senza perdita di generalità) che $n=p$ sia un primo, infatti se così non fosse si potrebbe ripetere il procedimento che segue più volte per ottenere $n$ composto (quello che intendo è che se vale per ${a^p-1} \over {a-1}$ allora vale per ${(a^p)^q-1} \over {a^p-1}$ e quindi per ${a^{pq}-1} \over {a-1}$).
Detto questo consideriamo allora $n=p$. Supponiamo che la tesi sia false e che quindi non ci siano "nuovi" fattori primi, allora per ogni $q$ primo tale che $q \mid a-1$ avremo per LTE che $$v_q(a^p-1)=v_q(a-1)+v_q(p)=\begin{cases} v_q(a-1)+1 \ ,\quad \mbox{se} \ q=p \\ v_q(a-1) \ ,\quad \mbox{se} \ q \ne p \end{cases}$$
Quest'ultima cosa ovviamente vale solo se $q$ è dispari, quindi dividiamo in due casi:
1) $a^p-1$ è dispari
Allora siccome ha gli stessi fattori primi di $a-1$ possiamo scrivere $$a^p-1=\prod_{q \mid a-1} q^{v_q(a^p-1)}= \begin{cases} a-1 \ , \quad \mbox{se} \ p \nmid a-1 \\ p(a-1) \ , \quad \mbox{se} \ p \mid a-1 \end{cases}$$
Nel primo caso avremo $a^p-1=a-1$ che è impossibile per $a>1$
Nel secondo caso invece $a^p-1=p(a-1)$ da cui $p=1+a+...+a^{p-1}$ che è impossibile, perché questo vorrebbe dire che $p>a$ e che quindi non potrebbe dividere $a-1$.
Ne concludiamo che allora la tesi è vera
2) $a^p-1$ è pari
Se $4 \mid a-1$ allora le ipotesi di LTE (nella forma classica) sono verificate, quindi posso ripetere lo stesso identico procedimento di prima.
Se invece $2 \| a-1$ avremo che, se $p$ è dispari allora $v_2(a^p-1)=v_2(a-1)=1$ così ci riconduciamo al caso 1, se invece $p=2$ allora $a^2-1=(a+1)(a-1)$ che (essendo la differenza fra i due fattori solamente 2) conterrà sempre un fattore primo diverso da $a-1$ a meno che non siano entrambi potenze di 2, quindi se $a=3$. (qui ci viene fuori l'eccezione $p=2$ , $a=3$)

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite