OliForum Matematico

Siccome alle olimpiadi di matematica è importante fare anche dimostrazioni e io non ho idea di come vadaro fatte , avevo pensato che potevo prendere un problema e provare a dimostrarlo coi vostri aiuti e consigli.
il problema è questo:
•a) Trovare tutti i numeri naturali n tali che $ 2^n -1 $ è un multiplo di 7
•b) Dimostrare che non c’è nessun naturale n tale che $ 2^n +1 $ è un multiplo di 7.

a)prima osservazione : noto che 7 è $ 2^3 -1^3 = (2-1)(4+1+2) = 1*7 = 7 $.
siccome $ (2^3 - 1^3) = 7 $ allora $ (2^3 - 1^3)^x = 7^x $ pero' il problema chiede di trovare tutti gli n e questo passaggio è inutile.

Allora prendiamo di nuovo $ 2^3 -1^3 = (2-1)(4+1+2) = 1*7 = 7 $ che ne consegue che $ (2^3)^n - 1=(2^n - 1)(4^n + 1 + 2^n) $ = multiplo di 7 , percio' tutti gli n devono essere multipli di 3

b)posso notare che il precedente di 7 non è una potenza di 2(elevato con un naturale) ma soltanto un suo multiplo , infatti $ 7 = 2*3 + 1 $.
Inoltre , $ 7 * $ ( un numero pari ) diminuito di 1 da un numero dispari e le potenze di 2 non sono dispari .
invece 7 * un numero dispari diminuito di 1 mi dara ' sempre un numero che si ottienre = 2 * [ 3 + ( un multiplo di 7 )]

immagino che non sia completo o ben fatto siccome è la prima dimostrazione su cui mi esercito.
tutti i consigli son ben accolti

Sulla parte a) ho capito poco... Anche se pare una specie di induzione.. Prova a spiegarti meglio
Per la parte b) non hai motivato la tua ultima affermazione (ok, è un passaggio, ma non è immediato), e poi, più importante, devi dimostrare che anche $7n+3$ non è mai una potenza di 2

Per il punto a, il testo dice di trovRe tutti gli $ n $. Quel tipo di dimostrazione dice che gli $ n $ sono multipli di 3, che alla fine è la soluzione, ma dovresti dimostrare che se n non è multiplo di 3 allora non va bene l'uguaglianza.
Edit: per il punto a e b, penso che la strada più easy siano le congruenze. Per le prime cose dirai:"hanno fatta la scoperta dell acqua calda". Ma dopo diventano interessanti e risolvono molti problemi

Usa le congruenze!

www.dm.unipi.it/~abbondandolo/divulgazione/congru.pdf

ok , ho dato un'occhiata alle congruenze . Ora riprovo
a)allora io devo trovare gli n tali che $ 2^n - 1 = 7x $.
$ 2^0 \equiv 1 \pmod{7} $ 1-1 non è un multiplo di 7
$ 2^1 \equiv 2 \pmod{7} $ 2-1 non è mult. di 7
$ 2^2 \equiv 2*2 \pmod{7} $ 4 -1 non è multiplo di 7
$ 2^3 \equiv 2*2*2 \equiv 1\ (mod{7}) $ cio' vuol dire che $ 2^3 $ diviso 7 mi da resto 1 e quindi se sottraiamo 1 da $ 2^3 $ otterremo un numero divisibile per 7. e infatti noi dobbiamo sottrarre 1 dal nostro $ 2^n $ per ottenere un multiplo di 7.
Dato che$ 2^3 $ è congruo a 1 allora $ (2^3)^x\equiv 1^x \equiv 1\ (mod 7 ) $ . gli n che cerchiamo sono multipli di 3.

poi non ho idea di come continuare e se quanto ho scritto sia accettabile. dovrei studiarmi meglio le congruenze ... nonostante cio' ,ci sarebbe qualcuno che mi risolverebbe questo esercizio in modo che io apprenda qualcosina in piu'?

Se $(a,b)=1$ allora l $ord_b(a)$ e quel k tale che $a^k \equiv 1 \pmod b$. Se a e b sono rispettivamente 2 e 7 ti sei accorto che k=3, percio stai sicuro che $2^n \equiv 1 \pmod 7 \Rightarrow n \equiv 0 \pmod 3$, per il fatto che l ordine moltiplicativo si ripete periodicamente (siccome $a^0 \equiv 1 \pmod b$ e dato che l ordine moltiplicativo dice a quale k si verifica che $a^k \equiv 1 \pmod b$)

Dimostrare invece che $2^n+1 \equiv 0 \pmod 7$, cioe $2^n \equiv 6 \pmod 7$. quando scrivi le potenze di 2 modulo 7, ci si accorge che sono 1,2,4 e basta, percio non sono mai congrui a 6, percio non esistono $n$ che soddisfano! Non e rigorosa come dimostrazione, attendo qualcuno piu esperto, ma questo e il succo!!

scambret ha scritto:Se $(a,b)=1$

vuol dire a modulo b = 1 ?
e...

allora l $ord_b(a)$

che vuol dire? ....
perdona la mia scarsa conoscenza

No problem! Allora (a,b)=1 significa che a e b sono coprimi, cioe che il MCD = 1. $ord_b(a)$ invece e quel k di cui ti parlavo, che prende il nome di ordine moltiplicativo

Sì, basta controllare i valori delle potenze da 1 a (in questo caso) $ord_7(2)=3$
Ovvero, per avere un modo pratico: continui a vedere le potenze di un numero modulo qualcosa finchè non vedi che si ripetono A quel punto se ce n'è statsa qualcuna che soddisfava, ok, altrimenti non c'è speranza che la tua proposizione si possa avverare

Drago96 ha scritto:Sì, basta controllare i valori delle potenze da 1 a (in questo caso) $ord_7(2)=3$
Ovvero, per avere un modo pratico: continui a vedere le potenze di un numero modulo qualcosa finchè non vedi che si ripetono A quel punto se ce n'è statsa qualcuna che soddisfava, ok, altrimenti non c'è speranza che la tua proposizione si possa avverare

Ma il metodo per dimostrare che si ripetono e che se $a^1 \equiv b \pmod c$ e $a^k \equiv 1 \pmod c \Rightarrow a^{k+1} = a^k * a^1 \equiv 1*b \equiv b \pmod c$? Puo andare?

scambret ha scritto:Ma il metodo per dimostrare che si ripetono e che se $a^1 \equiv b \pmod c$ e $a^k \equiv 1 \pmod c \Rightarrow a^{k+1} = a^k * a^1 \equiv 1*b \equiv b \pmod c$? Puo andare?

Esatto

Almeno questa

c'è ancora una cosa che non ho capito... a che cosa serve il fatto che a e b abbiamo come mcd 1?
senza questo riuscirei comunque a risolverlo, siccome devo trovare $ 2^n $ congruo 8 (mod 7) e quindi $ 2^n $ congruo a 1.
non vedo il collegamento...