Pagina 1 di 1

Massima potenza di 2 e parità

MessaggioInviato: 28/09/2017, 17:06
da vmaestrella
Dimostrare che se [tex]ab=2^n-1[/tex] e [tex]2^k[/tex] è la massima potenza di [tex]2[/tex] tale che [tex]2^k\mid 2^n-2+a-b[/tex], allora [tex]k[/tex] è pari.

Re: Massima potenza di 2 e parità

MessaggioInviato: 28/09/2017, 18:03
da matpro98
Testo nascosto:
Intanto [tex]ab=2^n-1 \Rightarrow 2^n-2+a-b=(a-1)(b+1)[/tex], quindi ti fai i due casi in cui [tex]n[/tex] sia pari (altri due sottocasi) o dispari

Re: Massima potenza di 2 e parità

MessaggioInviato: 28/09/2017, 18:35
da vmaestrella
Grazie matpro98, peró sinceramente non ho capito come concludere...
cioè $2^k|(a-1)(b+1) $ peró come faccio quindi ad analizzare esattamente il caso $n $ pari e $n $ dispari?

Re: Massima potenza di 2 e parità

MessaggioInviato: 28/09/2017, 23:10
da matpro98
Okay no aspetta ahahah facendolo a mente ho risolto solo un caso particolare e non l'intero problema. Sorry, ci penso su

Re: Massima potenza di 2 e parità

MessaggioInviato: 28/09/2017, 23:53
da Giovanni98
Da ciò che ha dedotto matpro98 si può concludere facilmente così. $2^k || (a-1)(b+1) \Rightarrow (a-1)({2^n}-1+a)$ poichè $a$ è dispari. Ma $(a-1)({2^n}-1+a) = (a-1)2^n - (a-1)^2$. Ora è ovvio che sia una potenza di $4$ a dividere esattamente $(a-1)^2$ quindi se dimostriamo che $v_2((a-1)2^n))>v_2((a-1)^2)$ abbiamo finito. Notiamo che $v_2((a-1)2^n) = v_2(a-1) + n$ e che $v_2((a-1)^2) = 2v_2(a-1)$ quindi ci basta dimostrare che $n > v_2(a-1)$ il che è ovvio se $b\ne 1$ poichè $2^n\ge 3a+1$. Se $b=1$ invece abbiamo che $2^k || 2^n-2+2^n-2 = 2^{n+1}-4 = 4(2^{n-1}-1)$ che da comunque $k$ pari quindi fine.

Re: Massima potenza di 2 e parità

MessaggioInviato: 01/10/2017, 11:24
da vmaestrella
Grazie Giovanni98, ma non ho capito la parte finale. :(
Non ho capito perchè
$n>v_{2}(a-1)$ puoi spiegarlo meglio perfavore?
(e poi perchè $2^{n}\geq 3a+1$?)

Re: Massima potenza di 2 e parità

MessaggioInviato: 01/10/2017, 20:44
da matpro98
Per la prima domanda, considera che $a $ è un fattore di $2^n $. Per la seconda, $2^n=ab+1$, ma se $b\neq 1$, allora $b\geq 3$