1)

• $97x\equiv13(mod\,105)$
  affinchè la congruenza ammetta soluzioni c'è bisogno che MCD(105,97) divida 13
  in questo caso abbiamo MCD(105,97)=1 che divide 13 per cui la congruenza ammette soluzioni;
  la congruenza corrisponde a dire che $97x$ diviso $105$ da come resto $13$;
  ossia $97x=105y+13 \quad\Rightarrow\quad 13=97x-105y$
  troviamo anzitutto una soluzione particolare della diofantea utilizzando l'algoritmo di Euclide a contrario;
  l'algoritmo di Euclide applicato tra 105 e 97 è il seguente:
  $105=97+8 \\97=12\cdot8+1\\8=8\cdot1+0$
  
  per applicarlo a contrario isoliamo i resti nelle prime 2 uguaglianze:
  $8=105-97\\1=97-12\cdot8$
  
  sostituendo la 1° nella 2° si ha:
  
  $1=97-12(105-97)=97\cdot13-105\cdot12$
  
  moltiplicando l'uguaglianza per 13 si ha:
  
  $13=97\cdot169-105\cdot156$
  
  abbiamo trovato la nostra sol. particolare $x=169$ e $y=156$
  pertanto tutte le possibili soluzioni della congruenza saranno del tipo
  
  $169+105k \quad\quad \forall k\in Z$
  
  (in questo caso abbiamo un'unica espressione che esprime la soluzione, a differenza dei sistemi di congruenze lineari)
• $12x\equiv 33 (mod\,57)$
  in tal caso si ha $MCD(12,57)=3|33$ per cui la congruenza ammette soluzioni; inoltre poichè MCD è diverso da 1, allora la congruenza è semplificabile;
  dividendo per 3 otteniamo l'equivalente:
  $4x\equiv 11 (mod\, 19)$
  da cui ricaviamo la diofantea $11=4x+19y$
  Applichiamo l'algoritmo di Euclide a 19 e 4:
  $19=4\cdot4+3\\4=3+1\\3=3\cdot1+0$
  da cui
  $1=4-3=4-(19-4\cdot4)=4\cdot5+19$
  moltiplichiamo per 11:
  $11=4\cdot55+19\cdot11$
  la nostra sol.particolare è $x=55$
  le possibili soluzioni della congruenza sono del tipo
  $55+19k \quad\quad\forall \kappa \in Z$
• $14x\equiv1 (mod\, 77)$
  $MCD(77,14)=7$ che non divide 1 pertanto la congruenza non ammette soluzioni

Dalle soluzioni trovate è facile ricavare la minima soluzione non negativa.

Voglio segnalare i seguenti appunti che ho trovato sulla rete, e che mi hanno chiarito (almeno credo) ogni residuo dubbio sulle congruenze lineari:

http://www.dm.unipi.it/~gaiffi/lmm_2005 ... azioni.pdf

...

Yesss... mirabile
Molto interessanti, gli appunti che segnali: grazie!

Riguardando la congruenza 1.(3), si potrebbe ottenere facilmente
una prima soluzione anche osservando che $\small \, 20=4\cdot 5\equiv 1\; (mod \, 19)\,$
e quindi $\small \, 4\cdot 55\equiv 11\; (mod \, 19)\,$...

A domani!

2)
Trovare il resto significa trovare un $r$ tale che
$(102^{73}+55)^{37}\equiv r (mod \,111)$

eleviamo ambo i membri al cubo; otteniamo:

$(102^{73}+55)^{111}\equiv r^3 (mod \,111)$

ora se dimostriamo che $111$ e coprimo con $102^{73}+55$, ossia $MCD(102^{73}+55,111)=1$, allora per il teorema di Fermat si ha che
$(102^{73}+55)^{111}\equiv 0 (mod \,111)$ da cui $r=0$
in realtà i due numeri sono proprio coprimi; infatti:
$111=37\cdot3$
quindi affinchè siano coprimi c'è bisogno che $102^{73}+55$ non sia divisibile nè per 3, nè per 37;

• non divisibilità per 3
  si nota che 102 è divisibile per 3 quindi lo sarà anche $102^{73}$;
  ma siccome 55 non è divisibile per 3, allora non lo sarà neanche $102^{73}+55$
• non divisibilità per 37
  la divisibilità per 37 implica che $102^{73}+55\equiv 0 (mod 37)$ $\quad\Rightarrow\quad 102^{73}\equiv -55 (mod 37) \quad\Rightarrow\quad 102^{73}\equiv 18 (mod 37)$
  
  moltiplichiamo ambo i membri per 102;
  si ottiene:
  $102^{74}\equiv 18\cdot102 (mod 37) \quad\Rightarrow\quad (102^2)^{37}\equiv 18\cdot102 (mod 37)$
  si nota che $MCD(102,37)=1$ per cui anche $MCD(102^2,37)=1$ ;Quindi per Fermat si ha
  $(102^2)^{37}\equiv 0 (mod 37)$
  per la divisibilità invece deve essere
  $102^{74}\equiv 18\cdot102 (mod 37)$
  siccome $18\cdot 102$ non è divisibile per $37$ se ne deduce che
  $102^{73}+55$ non è divisibile per $37$.

quindi ciò dimostra che $111$ e coprimo con $102^{73}+55$
per cui il resto cercato è 0.

Admin

3)

si nota che $216=3^3\cdot 2^3$;

sappiamo che $13^2 \equiv 17 (mod\,19)\equiv -2 (mod 19)$; quindi

$13^8 \equiv (-2)^4 (mod 19)\equiv 16 (mod 19)\equiv -3 (mod 19)$

elevando a 27 si ha:

$13^{216} \equiv (-3)^{27} (mod 19)\equiv (-27)^{9} (mod 19)\equiv (-8)^{9} (mod 19)\equiv ((-8)^3)^3 (mod 19)\equiv (-512)^3 (mod 19)\\ \equiv (-18)^3 (mod 19)\equiv 1^3 (mod 19)$

il resto è 1.

Admin

Visto che nessuno li risolve,
risolvo anche gli ultimi 2:

4)

lo si può risolvere considerando che

$3^2 \equiv -3 (mod\,12)$
$3^4 \equiv (-3)^2 (mod\,12) \equiv -3 (mod\,12)$
$3^8 \equiv (-3)^4 (mod\,12) \equiv -3 (mod\,12)$

ossia

3 elevato ad una qualsiasi potenza di 2 è pari a -3, modulo 12.

Per cui si ottiene:

$3^{400} \equiv (3^{16})^{25} (mod\,12) \equiv (-3)^{25} (mod\,12) \equiv (-3)^8\cdot(-3)^8\cdot(-3)^8\cdot(-3) (mod\,12) \\ \equiv (-3)\cdot(-3)\cdot(-3)\cdot(-3) (mod\,12) \equiv (-3)^4 (mod\, 12) \equiv -3 (mod\,12) \equiv 9 (mod\, 12)$

per cui l'ultima cifra di $3^{400}$ in base $12$ è $9$.

5)

Siccome $MCD(29,17)=1|1$, allora la congruenza ammette soluzione;
essendo $MCD(29,17)=1$ la congruenza non è ulteriormente semplificabile.
Essa corrisponde alla diofantea
$1=17r+29y$ (si può usare anche il segno -; non cambia nulla)
troviamo una soluzione particolare utilizzando l'algoritmo di Euclide:
$29=17+12\\17=12+5\\12=5\cdot2+2\\5=2\cdot2+1\\2=1\cdot2+0$
da cui i resti
$12=29-17\\5=17-12\\2=12-5\cdot2\\1=5-2\cdot2$
e quindi

$1=5-2\cdot2=(17-12)-2\cdot(12-2\cdot5)=(17-29+17)-2\cdot[(29-17)-2\cdot(17-29+17)]=\\=2\cdot17-29+2\cdot17-2\cdot29-8\cdot17-4\cdot29=12\cdot17-7\cdot29$
abbiamo ricavato la soluzione particolare$r=12$
essendo, quindi tutte le possibili soluzioni della congruenza, del tipo
$12+29k\quad\quad\forall k\in Z$
si ha che l'unico $r$ naturale minore di 29 che soddisfa la congruenza è proprio $12$.

Bruno,
ancora grazie per i quiz.

Mi spiace che siano interventuti in pochi a questo topic.

Ciao
Admin

Admin ha scritto:Mi spiace che siano intervenuti in pochi a questo topic.

...e a me fa invece molto piacere che tu ti sia divertito
Ciao!