Imo '64

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
fraboz
Messaggi: 90
Iscritto il: 09 giu 2010, 21:24
Località: reggio emilia

Imo '64

Messaggio da fraboz »

a) Trova tutti gli interi positivi $ n $ tali che $ 7|2^n-1 $
b) Dimostra che per ogni intero positivo $ n $, $ 7\not| 2^n+1 $
Avatar utente
ale.G
Messaggi: 66
Iscritto il: 22 nov 2010, 15:14
Località: Lunghezza

Re: Imo '64

Messaggio da ale.G »

Vado col pr-imo :mrgreen: :
se pongo $2^n-1=7$ allora verrà $n=3$. Se n fosse pari posso anche scomporre $2^n-1$ in $(2^{\frac{n}{2}}-1)(2^{\frac{n}{2}}+1)$. Da qui se eguaglio il secondo fattore a 7 (poichè esso è primo) mi verrà un $n$ non intero ma se eguaglio a $7$ il primo mi verrà $n=6$. Da qui vedo che i primi risultati sono entrambi multipli di tre,allora provo a mettere direttamente $2^{3n}-1=7k\implies 8^n-1=7k$. Questo si dimostra per induzione, senza che illustro il procedimento.
Per il secondo punto ragiono per assurdo:pongo $2^n+1=7k$ e provo a farlo per induzione. $2^{n+1}+1=7k \implies 2(7k_1-1)+1=7k_2$ ma sappiamo con certezza che $14k_1-1$ non è divisibile per 7, da cui la tesi.

Spero al solito di averci preso :roll:
I tuoi problemi te li puoi anche tenere: a me, invece, non dispiacerebbe avere un camper come questo !
paga92aren
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: Imo '64

Messaggio da paga92aren »

a) Calcolo i resti modulo 7 delle potenze di 2 e sono 2,4,1 quindi hanno periodo 3.
$2^{3k}\equiv 1 \mod 7 \Leftrightarrow 7|2^{3k}-1$ quindi vale per tutti gli $n$ multipli di 3.
b) $2^n\equiv -1 \equiv 6 \mod 7$ ma i resti sono solo 1,2,4 quindi è impossibile che esista $n$
Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Re: Imo '64

Messaggio da julio14 »

ale.G ha scritto:Spero al solito di averci preso :roll:
Mi spiace, non ci hai preso :D se non ti offendi, provo a dirti cosa c'è che non va.
ale.G ha scritto:se pongo $2^n-1=7$ allora verrà $n=3$. Se n fosse pari posso anche scomporre $2^n-1$ in $(2^{\frac{n}{2}}-1)(2^{\frac{n}{2}}+1)$. Da qui se eguaglio il secondo fattore a 7 (poichè esso è primo) mi verrà un $n$ non intero ma se eguaglio a $7$ il primo mi verrà $n=6$.
Fino a qua ok, anche se è inutile ai fini della soluzione. Per vedere i casi piccoli, era forse più semplice iniziare a mettere dentro n=1,2,3...
ale.G ha scritto:provo a mettere direttamente $2^{3n}-1=7k\implies 8^n-1=7k$. Questo si dimostra per induzione, senza che illustro il procedimento.
Questo è giusto, il problema è che, per come hai fatto il secondo punto, non sono sicuro ti sia chiarissimo come funziona l'induzione: perché non provi a esplicitare il passaggio?
Inoltre il primo punto non è completo: con l'induzione dimostri che tutti i multipli di 3 vanno bene, ma non che gli n non multipli di 3 non vanno bene. Cioè, hai dimostrato che tutti i multipli di 3 funzionano, ti manca da dimostrare che sono i soli a funzionare.
ale.G ha scritto:Per il secondo punto ragiono per assurdo:pongo $2^n+1=7k$ e provo a farlo per induzione. $2^{n+1}+1=7k \implies 2(7k_1-1)+1=7k_2$ ma sappiamo con certezza che $14k_1-1$ non è divisibile per 7, da cui la tesi.
Ecco, qua hai proprio sbagliato. Intanto hai dimenticato di fare il caso base, ma comunque il passo induttivo è sbagliato: tu hai detto "$ 7 $ divide $ 2^n+1 $ implica $ 7 $ non divide $ 2^{n+1}+1 $" mentre il passo induttivo giusto sarebbe "$ 7 $ non divide $ 2^n+1 $ implica $ 7 $ non divide $ 2^{n+1}+1 $". In ogni caso, da questo approccio non si riesce a concludere, nel senso che l'ipotesi induttiva "$ 7 $ non divide $ 2^n+1 $" non ti aiuta. Qui devi guardare il problema da un altro punto di vista, ad esempio con le congruenze come ha fatto paga2aren.
Rispondi