Soluzioni non congrue modn

[Shepard1]

Ciao ragazzi, sono alle prese con un fastidiosissimo calcolo delle soluzioni non congrue.

Dato ax congro b mod(n) sappiamo che ci sono (a,n) soluzioni non congrue.

Se ad esempio ci troviamo davanti a 95x$-=$57(mod114) il MCD(95,114)=19=d

Questo ci dice che l'equazione ha 19 soluzioni NON congrue.

Ok, ma quale è la formula per calcolarle?

La formula per le soluzioni è: $x_0$ * k$\bar n$ dove $\bar n$=n/d

In questo esercizio sappiamo che $x_0$=3 e $\bar n$ = 6

Quindi le soluzioni sono 6+3k, con k che varia in N. Però queste sono tutte le soluzioni congrue. Quelle NON congrue come le calcolo?

Grazie ragazzi

[dissonance]

Cioè, vediamo di tradurre in linguaggio più preciso. Tu hai capito che le soluzioni della congruenza

\[95 x \equiv 57 \mod 114\]

sono \(x=3+6k,\ k \in \mathbb{Z}\). E queste qua sono tutte le soluzioni, mi ritrovo coi tuoi calcoli. Adesso vuoi trovare un sistema completo di rappresentanti mod 114 per queste soluzioni?

Se sai già che le soluzioni sono 19, allora ti basta fare viaggiare \(k\) da \(0\) a \(18\). Infatti per \(k=18\) hai \(3+6\cdot 18=111 < 114\) quindi per \(k\) da \(19\) in poi le soluzioni iniziano a ripetersi modulo \(114\).

[Shepard1]

Purtroppo io sto solo ripetendo quello che ha spiegato la prof, la mia imprecisione viene da questo.

Dunque io dovrei svolgere la congruenza lineare come di consueto e mostrare d soluzioni, dove d è il MCD(a,n).

La differenza tra congrue e non congrue sta nel fatto che a partire dalla soluzione d+1 iniziano a ripetersi da quanto ho capito.

Perfetto, grazie

[dissonance]

Si, guarda, fai la prova per rendertene conto. Per \(k=0\) hai la soluzione \(x_0=3\). Per \(k=1\) hai \(x_1=9\) e così via fino a \(k=18\) che ti dà \(x_{18}=111\). Adesso prendi \(k=19\) ottenendo \(x=117\) che è congruo a \(3\) modulo \(114\). Ecco che rispunta \(x_0\). Aumentando \(k\) ora continuerai a ritrovare le soluzioni \(x_0 \ldots x_{18}\) modulo 114.