Divisibilità
salve a tutti...non sono sicuro che questa sia la sezione giusta...nel caso non lo sia chiedo scusa anticipatamente ai moderatori
veniamo al dunque. in queste ultime settimane a scuola stiamo trattando il tema della crittografia e il docente ha deciso di analizzare uno dei sistemi più usati oggi in questo senso: RSA. in questo senso ci ha spiegato tutto bene bene ma ci sono alcune cose che non mi quadrano ancora perfettamente, soprattutto quello che riguarda la divisibilità. Più precisamente il prof di recente ha messo un esercizio in cui viene affermato il seguente: la somma di tutti i numeri minori di 2009, coprimi rispetto a 2009, è divisibile da 2009. Ho cercato di trovare una spiegazione ma non riesco. qualcuno potrebbe gentilmente indirizzarmi sulla retta via?
veniamo al dunque. in queste ultime settimane a scuola stiamo trattando il tema della crittografia e il docente ha deciso di analizzare uno dei sistemi più usati oggi in questo senso: RSA. in questo senso ci ha spiegato tutto bene bene ma ci sono alcune cose che non mi quadrano ancora perfettamente, soprattutto quello che riguarda la divisibilità. Più precisamente il prof di recente ha messo un esercizio in cui viene affermato il seguente: la somma di tutti i numeri minori di 2009, coprimi rispetto a 2009, è divisibile da 2009. Ho cercato di trovare una spiegazione ma non riesco. qualcuno potrebbe gentilmente indirizzarmi sulla retta via?
Risposte
Ciao!
Si' e' la sezione giusta.
Osserva che se $a$ e' un numero minore di $2009$ coprimo con $2009$ allora anche $2009-a$ e' minore di $2009$ e coprimo con $2009$. Questo ti dovrebbe suggerire qualcosa...
Si' e' la sezione giusta.
Osserva che se $a$ e' un numero minore di $2009$ coprimo con $2009$ allora anche $2009-a$ e' minore di $2009$ e coprimo con $2009$. Questo ti dovrebbe suggerire qualcosa...
"Martino":
Ciao!
Si' e' la sezione giusta.
Osserva che se $a$ e' un numero minore di $2009$ coprimo con $2009$ allora anche $2009-a$ e' minore di $2009$ e coprimo con $2009$. Questo ti dovrebbe suggerire qualcosa...
uhm, allora, vediamo se ho capito:
devo dimostrare che $1 + 2 + 3 + ... + 2008$ (ammesso che quelli tra i puntini siano coprimi con 2009) dunque procedo ne modo seguente:
$(1 + 2008) + (2 + 2007) + (3 + 2006) + ...$
ora, tutta la sommatoria deve essere divisibile per 2009...dunque dal momento tutti le coppie sono divisibili per 2009 anche la somma lo è. Ok, ci sono
mi permetto allora di chiedere un'alta cosa (stesso corso, stesso prof, stesso tema):
devo dimostrare che se $n$ è un numero dispari allora $a^n + b^n$, $a$ e $b$ interi positivi, è divisibile per $a + b$: un altro indizio?
Se riduci modulo $a+b$ hai che $b equiv -a$...
Se non conosci l'aritmetica modulare allora puoi vedere $a^n+b^n$ come polinomio: se vedi per esempio $a$ come un'incognita e $b$ come un valore noto allora $a^n+b^n$ ha $-b$ come zero, ed ora non resta che applicare Ruffini.
Se non conosci l'aritmetica modulare allora puoi vedere $a^n+b^n$ come polinomio: se vedi per esempio $a$ come un'incognita e $b$ come un valore noto allora $a^n+b^n$ ha $-b$ come zero, ed ora non resta che applicare Ruffini.
si, conosco l'aritmetica modulare. il problema dunque potrebbe porsi come:
$a^n + b^n = 0 mod (a + b)$
devo dimostrare questo giusto?
poniamo $a + b = m$
$(a^n + b^n) * x = 0 + k * m$
dunque:
$(a^n + b^n) * x + k*c = 0$
potrebbe portarmi alla soluzione se applicassi il teorema del resto cinese o mi sto solo perdendo (la seconda mi sembra la più possibile
)?
$a^n + b^n = 0 mod (a + b)$
devo dimostrare questo giusto?
poniamo $a + b = m$
$(a^n + b^n) * x = 0 + k * m$
dunque:
$(a^n + b^n) * x + k*c = 0$
potrebbe portarmi alla soluzione se applicassi il teorema del resto cinese o mi sto solo perdendo (la seconda mi sembra la più possibile
)?
Se conosci l'aritmetica modulare allora dovresti capire i seguenti passaggi: definito $m=a+b$ hai $b -= -a\ \mod(m)$ e quindi
$a^n+b^n -= a^n+(-a)^n -= a^n-a^n -= 0\ \mod(m)$.
$(-a)^n=-a^n$ perche' $n$ e' dispari.
$a^n+b^n -= a^n+(-a)^n -= a^n-a^n -= 0\ \mod(m)$.
$(-a)^n=-a^n$ perche' $n$ e' dispari.
allora, credo di essermi perso un attimino...ricapitolando:
devo dimostrare che:
$a^n + b^n -= 0 mod (a + b)$
ora pongo $m = a + b$ e dunque ottengo la seguente eguaglianza:
$b -= -a mod(m)$ (1)
dunque:
$a^n + b^n = a^n + (-a)^n$ secondo (1)
quindi dal momento che $n$ è dispari ottengo che:
$(-a)^n = -a^n$
e dunque arrivo a:
$a^n-a^n -= 0 mod(m)$ dal momento che $a^n-a^n = 0$
per vedere se ho capito voglio provare a fare lo stesso ragionamento ma ponendo $n = 4*k + 2$ e stavolta $a^n + b^n$ deve essere divisibile per $a^2 + b^2$
devo sempre dimostrare che:
$a^n + b^n -= 0 mod (m)$
dove $m = a^2 + b^2$
=> $b^2 = -a^2 mod (m)$ (1)
dunque:
$a^(4 * k + 2) + b^(4 * k + 2)$ (2)
sostituisco (1) in (2) e ottengo:
$a^(4 * k + 2) + b^(2 * (4 * k + 2)) = a^[2* (2 * k + 1)] + b^[4 * (2 * k + 1)] -= 0 mod (m)$
dal momento che sia $4 * k + 2$, sia $2 * (4 * k + 2)$ sono sempre pari come faccio ad affermare che $a^(4 * k + 2) + b^(2 * (4 * k + 2))$ è divisibile per $a^2 + b^2$?
devo dimostrare che:
$a^n + b^n -= 0 mod (a + b)$
ora pongo $m = a + b$ e dunque ottengo la seguente eguaglianza:
$b -= -a mod(m)$ (1)
dunque:
$a^n + b^n = a^n + (-a)^n$ secondo (1)
quindi dal momento che $n$ è dispari ottengo che:
$(-a)^n = -a^n$
e dunque arrivo a:
$a^n-a^n -= 0 mod(m)$ dal momento che $a^n-a^n = 0$
per vedere se ho capito voglio provare a fare lo stesso ragionamento ma ponendo $n = 4*k + 2$ e stavolta $a^n + b^n$ deve essere divisibile per $a^2 + b^2$
devo sempre dimostrare che:
$a^n + b^n -= 0 mod (m)$
dove $m = a^2 + b^2$
=> $b^2 = -a^2 mod (m)$ (1)
dunque:
$a^(4 * k + 2) + b^(4 * k + 2)$ (2)
sostituisco (1) in (2) e ottengo:
$a^(4 * k + 2) + b^(2 * (4 * k + 2)) = a^[2* (2 * k + 1)] + b^[4 * (2 * k + 1)] -= 0 mod (m)$
dal momento che sia $4 * k + 2$, sia $2 * (4 * k + 2)$ sono sempre pari come faccio ad affermare che $a^(4 * k + 2) + b^(2 * (4 * k + 2))$ è divisibile per $a^2 + b^2$?
Non hai sostituito bene (1) in (2).
si vero, hai ragione...dunque dal momento che $(-a^2)^n$ dove $n$ è un numero pari ottengo che:
$a^(2 * (2 * k + 1)) + a^(4 * ( 2 * k + 1))$ (3)
ora se è vero che ho $b^2 -= -a^2 mod(m)$ allora:
$a^2 + b^2 = a^2 + a^2$ (4)
ora devo dimostrare che (3) è divisibile per (4)...sarà che sono le 18 passate e che sono in biblioteca da dopo pranzo, ma proprio non vedo come
$a^(2 * (2 * k + 1)) + a^(4 * ( 2 * k + 1))$ (3)
ora se è vero che ho $b^2 -= -a^2 mod(m)$ allora:
$a^2 + b^2 = a^2 + a^2$ (4)
ora devo dimostrare che (3) è divisibile per (4)...sarà che sono le 18 passate e che sono in biblioteca da dopo pranzo, ma proprio non vedo come
Se sostituisci $-a^2$ a $b^2$ allora $b^{4k+2}$ diventa $-a^{4k+2}$, no?
](/datas/uploads/forum/emoji/eusa_wall.gif "Brick wall")
oddio, hai ragione...forse è meglio che vado a fare compagnia alla macchinetta del caffe
grazie mille per l'aiuto Martino, molto gentile da parte tua
Prego! Alla prossima.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo