Problemi di divisibilità

[Pozzetto1]

Buongiorno a tutti,
piccolo problema riguardo la divisibilità sugli interi.

Se ho $a,b in NN$ con $b >=0$, devo completare: "Se il numero $a$ ha resto $r$ nella divisione per $b$, e $a+1$ non è divisibile per $b$, allora il resto della divisione di $a+1$ per $b$ è....."

Se qualcuno mi aiutasse a ragionarci sarei contento.

Grazie mille a tutti.

[Pozzetto1]

Potrebbe essere $r+1$?

[Frink1]

Esattamente $ r+1 $. Non è altro che un numero mod n...

[Pozzetto1]

Se invece dati $a,b,c in NN$ con $c>=0$ e $c|b$, devo dimostrare che il resto della divisione di $a+b$ per il numero $c$ è uguale al resto della divisione di $a$ per $c$.

Come lo fareste?

Io mi sono bloccato qua:

$b=cq+0$ perchè $c$ divide $b$
$a+b=qc + r$

e qui mi blocco...consigli?

Grazie

[Frink1]

$ a=dq+r $, $ b=cq $. Questo implica che $ a+b=cq+dq+r $ ossia $ a+b=(c+d)q+r $, ed è dimostrato.

[Pozzetto1]

Grazie Frink,

se invece ho $a,b,c in NN$ con $c>=0$ e sia $r$ il resto della divisione di $a$ per $c$ e $s$ il resto della divisione di $b$ per $c$. E' sempre vero che il resto della divisione di $a+b$ per $c$ è uguale a $r+s$ ? Se non è vero, come calcolarlo se non vogliamo fare la divisone di $a+b$ per $c$ ma conosciamo $r$ ed $s$?

IO ho fatto:

$a=cq+r$
$b=cq+s$

$a+b=cq+cq+r+s$.

Ma cosa posso trarre da questo?

Grazie infinite.

[Frink1]

Se $ r+s $ fosse uguale a $ q $, allora diventerebbe $ a+b=cq+dq+q=(c+d+1)q $ perciò $ a+b $ sarebbe divisibile per $ q $. Non può valere $ r+s=kq $ perché $ r,s

Cita

Segnala

[Pozzetto1]

"Frink":Se $ r+s $ fosse uguale a $ q $

... perchè dici questo?

[Frink1]

Poniamo ad esempio $ a=14, b=11 $ e $ q=5 $. Allora $ a=2*5+4 $, $ b=2*5+1 $. Ma i due resti danno $ 5 $ come somma. Infatti, sommando: $ 14+11=25=5*5+0 $, ossia come ho trasposto nel messaggio precedente i resti si sommano e possono essere divisi lasciando resto $ 0 $

EDIT: Ah, forse ho capito l'obiezione. Ho chiamato $ q $ il divisore che tu avevi chiamato $ c $, ti chiedo scusa

[Pozzetto1]

Countinuo a non capire come mai hai scelto $q$ oltre che ad $a$e a $b$...

EDIT: obiezione corretta..

[Frink1]

Facciamola facile: come ipotesi hai $ not(q|a)^^not(q|b) $ giusto? Allora entrambi possono essere scritti come $ a=cq+r^^b=dq+s $ con $ q $ divisore, $ r,s $ resti. Ora, se $ r+s $ è uguale a $ q $, capisci che vale $ a+b=cq+dq+(r+s)=cq+dq+q=(c+d+1)q $ e quindi che $ q|a+b $. Se invece $ r+s>q $...

[Pozzetto1]

"Frink":Facciamola facile: come ipotesi hai $ q|a^^q|b $ giusto?

Come ipotesi non ho che $q$ non divide ne $a$ ne $b$ ?

[Frink1]

Sì, ho scritto una baggianata, intendevo $ q $ divisore, perdonami, la fretta gioca brutti scherzi Ora correggo

[Pozzetto1]

Comincio a capire. MA come mai il resto $r+s$ lo hai chiamato $q$ ?

[Frink1]

Non l'ho "chiamato" $ q $. Ci sono tre possibilità (tricotomia) per la somma dei resti:

$ r+sq $.

Esaminiamole tutte e tre.

1. $ r+s
2. $ r+s=q $ è il caso che ho illustrato prima, implica $ q|a+b $

3. $ r+s>q $ ma comunque $ r+s<2q $ perché $ r,s
Capisci allora che se non hai i numeri di partenza, applicando queste tre possibilità hai piuttosto velocemente il resto della divisione della somma. Spero di essere stato chiaro

[Gi81]

Mi intrometto per riassumere:

"Pozzetto":se invece ho $a,b,c in NN$ con $c>=0$ e sia $r$ il resto della divisione di $a$ per $c$ e $s$ il resto della divisione di $b$ per $c$. E' sempre vero che il resto della divisione di $a+b$ per $c$ è uguale a $r+s$ ? Se non è vero, come calcolarlo se non vogliamo fare la divisone di $a+b$ per $c$ ma conosciamo $r$ ed $s$?

se $r+s mentre se $r+s>=c$ allora il resto della divisione di $a+b$ per $c$ è $r+s-c$.

P.S.: non ha senso che $c=0$

[Pozzetto1]

Ci ho pensato a lungo ma non riesco ancora a capire perchè $r+s

Cita

Segnala

[Frink1]

$ q $ indica il divisore che tu avevi chiamato $ c $. Chiamalo come vuoi, sempre quello resta.
Sai dalla teoria che il resto deve essere $ 0<=rpuò essere inferiore a $ q $ stesso, ad esempio se i resti fossero $ r=1,s=2 $ e fosse $ q=5 $, allora $ r+s<5 $. Ma possono essere anche uguali (es. $ r=2,s=3 $) o anche maggiori (es. $ r=4,s=4 $).

[Pozzetto1]

Ultima dimostrazione:

Devo dimostrare che dato un qualunque $n in NN$ ka sua fattorizzazione in numeri primi contiene al massimo $log(n)$ fattori.

In generale so che un qualunque numero può essere scritto come $n=p_1^(a_1)p_2^(a_2)p_3^(a_3)---p_k^(a_k)$

Quindi ho che $k<=log(n)$...poi?