77'. Proviamo questo

Numeri interi, divisibilità, primalità, ed equazioni a valori interi.

77'. Proviamo questo

Messaggioda Veritasium » 02/01/2017, 15:13

Determinare tutti gli interi positivi [tex]n > 1[/tex] per cui esiste un unico intero [tex]1 \le a \le n![/tex] tale che [tex]n! \mid a^n + 1[/tex]
Veritasium
 
Messaggi: 206
Iscritto il: 30/03/2015, 20:36

Re: 77'. Proviamo questo

Messaggioda Giovanni98 » 14/01/2017, 12:26

Risposta :
Testo nascosto:
$n$ soddisfa se e solo se è un numero primo.


Dimostrazione :
Testo nascosto:
Chiaramente se $n$ è pari ed è $\ge 4$ abbiamo che $a$ deve essere dispari. Tuttavia giungiamo ad un assurdo modulo $4$ poichè $a^n + 1 \equiv 2 \pmod 4$ dal momento che $n$ è pari $\ge 4$ e che quindi $4 \mid n!$ mentre $4 \nmid a^n+1$. Da cui $n = 2$ che da ovviamente soluzione in quanto l'unico valore possibile di $a$ è $1$.

Se $n$ è dispari e non primo allora esiste un primo dispari $p < \frac{n}{2} (\Rightarrow p^2 \mid n!)$ tale che $p \mid n$. Prendendo $a = n! - 1$ e $a = \frac{n!}{p} - 1$ possiamo subito notare che in ambo i casi la relazione di divisibilità $n! | a^n+1$ è soddisfatta (usufruendo di LTE per dimostrare il secondo caso).

Se $n$ è un primo $p$ dispari allora esiste un unico $a$ che soddisfa, ed è $p!-1$. Infatti, notiamo che se almeno un primo dispari $q \leq p$ è tale che $q \nmid a+1$ allora $p \mid q-1$ da cui $p \leq q-1 \leq p-1$ (sfruttando la nota relazione di divisibilità $ord_x(y) \mid x-1$ dove $x$ è un primo) da cui ovviamente assurdo. Quindi tutti i primi dispari $q \leq p$ sono tali che $q \mid a+1$, ma a questo punto è sufficiente LTE per dimostrare che se $q^r \mid \mid p!$ allora $q^r \mid a+1$. Nel caso in cui $q=2$ abbiamo che $v_2(a^p + 1) = v_2(a+1)$ dal momento che $a$ è dispari e che quindi $\sum_{i=0}^{p-1} a^i(-1)^{p-1-i} \equiv 1 \pmod 2$. Abbiamo di conseguenza dimostrato che $v_q(p!) \leq v_q(a+1)$ per ogni primo $q \leq p$ da cui ovviamente si ricava $a+1=p! \Rightarrow a = p!-1$ che è quindi l'unico intero $a$ che rispetta le condizioni del testo.
Avatar utente
Giovanni98
 
Messaggi: 1255
Iscritto il: 27/11/2014, 14:30

Re: 77'. Proviamo questo

Messaggioda Veritasium » 14/01/2017, 12:45

Buona!
Veritasium
 
Messaggi: 206
Iscritto il: 30/03/2015, 20:36

Re: 77'. Proviamo questo

Messaggioda Salvador » 17/02/2017, 23:10

Che cos'è LTE?
Salvador
 
Messaggi: 266
Iscritto il: 26/11/2016, 11:55


Torna a Teoria dei Numeri

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti