Correttezza "dimostrazione"

[utente__medio11]

Ciao, facendo pulizia sul desktop mi sono imbattuto in una questione ancora in sospeso.
Avevo già proposto la questione in un altro topic, ma senza ottenere alcun riscontro, probabilmente anche a causa di un discorso che viste le premesse poteva apparire dispersivo e poco chiaro. Ho deciso quindi di riprovarci cercando di semplificare al massimo.

Premesso che $mod$ è inteso come operatore binario (dove $a mod b$ restituisce il resto della divisione intera tra $a$ e $b$ col quoziente arrotondato verso l'infinito negativo), sapreste dirmi se la mia seguente "dimostrazione" è corretta?

Siano $a>b>0$ due interi, e sia $c$ un divisore di $ab-b$ che soddisfa le seguenti due condizioni

1) $c>b$
2) $a mod c=1$

Una soluzione sempre valida, e che massimizza $c$, è $c=a-1$; le altre soluzioni saranno invece costituite dai divisori di $a-1$ maggiori di $b$.
Introduciamo i due interi non negativi

3) $i 4) $j
Sfruttando la proprietà distributiva dell'operazione modulo rispetto all'addizione si ricava

5) [size=83]$[(a+i)(b+j)] mod c = (ab +ja + ib + ij) mod c = [(ab mod c) + (ja mod c) + (ib mod c) + (ij mod c)] mod c$[/size]

Dalla 1) e 2) si ricava

6) $ab mod c = b$

Dalla 2) e 4) (che in questo caso risulta più restrittiva del necessario, sarebbe infatti sufficiente $j
7) $ja mod c = j$

Dalla 3) si ricava

8) $ib mod c = ib$

Sostituendo la 6), 7) e 8) nella 5) e utilizzando la 4) (da cui si evince che $b+j+ib+ij
9) [size=85]$[(a+i)(b+j)] mod c = (b+j+ib+ij) mod c = b+j+ib+ij = (i+1)(b+j)$[/size]

-------------------------------------------------------------------------------------------------------------------------

OSSERVAZIONE 1: dalla 9) si ricava

10) [size=80]$MCD{(a+i)(b+j) \ , \ [(a+i)(b+j)] mod c} = MCD[(a+i)(b+j) \ , \ (i+1)(b+j)] =(b+j)*MCD(a+i \ , \ i+1)$[/size]

che restituisce come risultato $b+j$ nel caso in cui $a+i$ e $i+1$ sono coprimi, cosa che sarà sicuramente vera se $(a+i)(b+j)$ è un semiprimo.

-------------------------------------------------------------------------------------------------------------------------

OSSERVAZIONE 2: notando dalla 4) che al crescere di $i$ il limite superiore di $j$ diminuisce, e volendo trovare un limite superiore $m$ comune per entrambi, risolviamo la seguente equazione di secondo grado nella variabile $i$

11) $c/(i+1)-b=i$

Tale equazione ha due soluzioni, una positiva (chiamiamola $i'$ , che non sarà per forza una quantità intera) e una negativa, e ovviamente quella negativa va scartata essendo per ipotesi $i$ e $j$ interi non negativi. A questo punto sostituendo $i'$ nella 4) si otterrebbe $j
12) [size=120]\( m = \Bigl \lceil \frac{\sqrt{(b-1)^2+4c} \ -b-1}{2} -1 \Bigr \rceil \) [/size]

Poi se vi state chiedendo quale sia il senso di tutto ciò, vi spiego da dove nasce la questione: in pratica qualsiasi semiprimo $S$ dato dal prodotto di due primi $p_1$ e $p_2$ prelevati rispettivamente dai seguenti due intervalli

$[a \ ; \ a+m]$ e $[b \ ; \ b+m]$

può essere fattorizzato tramite la 10), ossia

$MCD(S \ , \ S mod c)=p_2$

Sull'utilità di questo risultato se ne potrà poi discutere, e volendo potrò chiarire anche il contesto in cui la questione è nata, ma per il momento vorrei capire se i passaggi riportati in quella "dimostrazione" siano corretti e non ulteriormente semplificabili.

[otta96]

Manca la giustificazione del fatto che $ij\modc=ij$, il resto mi sembra che vada tutto bene, se sia semplificabile però non lo so.

[utente__medio11]

"otta96":Manca la giustificazione del fatto che $ij\modc=ij$

"utente__medio":...e utilizzando la 4) (da cui si evince che $ b+j+ib+ij
Dalla suddetta disequazione, avendo a sinistra una somma di quantità non negative, si evince tra l'altro che $ij

Cita

Segnala

[otta96]

Si giusto.