...

Cogliendo lo spunto delle riflessioni di Pietro, Pasquale e Daniela (ved. topic
sulla "frazione limitata"), abbiamo da risolvere (se ci va...) queste congruenze:

1) Qual è il resto positivo della divisione di $\, 12345^{\tiny 12345}\,$ per $\,17$?

2) Trovare tutti i numeri naturali di tre cifre e terminanti con 7 tali che, dividendoli
per 3 e per 11, diano rispettivamente 1 e 2 come resto.

3) Quali sono le ultime due cifre di $\, 7040407^{\tiny 7447}$?

Pietro, Daniela... su

PS - Volendo, in questo interessante sito si possono trovare alcuni suggerimenti,
senza naturalmente dimenticare il prezioso contributo del nostro Gianfranco Bo.


Bruno

Ciao Bruno,
anzitutto ti ringrazio per i quiz e per l'interessante sito;
quanto alla pagina di Gianfranco è da lì che appresi, non molto tempo fa, che esisteva l'aritmetica modulare.

Dunque,
provo col n° 2:

i numeri da trovare devono terminare con 7, quindi sono del tipo $10c+7$;
inoltre devono essere tali che divisi per 3 danno come resto 1, cioè
$10c+7 \equiv1 \;(mod 3)$
e divisi per 11 danno come resto 2, cioè
$10c+7 \equiv2 \;(mod 11)$

quindi dobbiamo risolvere il sisitema

$\left{ 10c+7 \equiv1 \;(mod 3) \\ 10c+7 \equiv2 \;(mod 11)$

relativamente alla prima equazione $10c+7 \equiv1 \;(mod 3)$
si ha

$10c+7-7 \equiv1-7 \;(mod 3)\quad\Rightarrow\quad\ 10c \equiv -6 \;(mod 3)\quad\Rightarrow\quad\ 10c \equiv 0 \;(mod 3)$

da cui si evince che $10c$ deve essere divisibile per 3, ossia deve essere $c=3p$

sostituendo nella seconda equazione si ottiene

$10\cdot3p+7 \equiv2 \;(mod 11)$ da cui

$10\cdot3p+7-7 \equiv2-7 \;(mod 11)\quad\Rightarrow\quad30p\equiv-5 \;(mod 11)\quad\Rightarrow\quad30p\equiv6 \;(mod 11)$

ciò vuol dire che il numero $30p$ deve essere tale che diviso per 11 da come resto 6;
quindi deve appartenere alla classe di resto modulo 11 che contiene 6;
non ve ne è uno solo ma infiniti, e tutti appartengono a tale classe;
individuiamo il più piccolo numero $30p$ appartenente alla classe;

dunque, la classe contiene tutti i numeri interi del tipo $6+11\cdot k$;
per cui

$C_6={..., 6, 17, 28, 39, 50, 61, 72, ....}$

il più piccolo numero $30p$ appartenente alla classe è $30\cdot9=270$.

Quindi il più piccolo numero terminante con 7 e tale che diviso per 3 da resto 1 e per 11 da resto 2, è $270+7=277$;
quindi tutti i numeri interi positivi che soddisfano il problema dovrebbero essere del tipo

$277+3\cdot11\cdot k\quad\quad \forall \;k\ge 0 \in \aleph$

però non per tutti i valori di k i numeri terminano per 7;
per assicurare ciò c'è bisogno di moltiplicare anche per 10 in modo da avere $11\cdot3\cdot10=330$

per cui lo soluzione corretta è:

$277+330k\quad\quad \forall \;k\ge 0 \in \aleph$

però, ricordando anche la recente discussione sui resti negativi, c'è da considerare anche i negativi;
affinchè essi terminino per 7 c'è bisogno che siano del tipo $-10c-7$ con $c\ge0$
per cui in questo caso il sistema diventa

$\left{ -10c-7 \equiv1 \;(mod 3) \\ -10c-7 \equiv2 \;(mod 11)$

da cui
$\left{-10c-7+7 \equiv1+7 \;(mod 3)\quad\Rightarrow\quad -10c\equiv 8 (mod 3)\quad\Rightarrow\quad -10c\equiv 2 (mod 3) \\ -10c-7+7 \equiv2+7 \;(mod 11)\quad\Rightarrow\quad -10c\equiv 9 (mod 11)$

quindi $-10c$ deve appartenere sia alla classe di resto modulo 3 cui appartiene 2, sia alla classe di resto modulo 11 cui appartiene 9;
dobbiamo ricercare il numero solo tra quelli delle due classi che terminano con 0 dato che è del tipo $-10c$;
enumeriamo le classi andando verso i negativi:

$[C_2]_3={..., 2, -1, -4, -7, -10, ..., -40, ..., -70,..., -100, ..., ..., -310, ...}$
$[C_9]_11={..., 9, -2, -13, -24, -35, -46, -57, -68, -79, -90, ..., -200, ..., -310, ...}$
quindi il più piccolo intero negativo appartenente alle 2 classi del tipo -10c è -310;
Il più piccolo intero negativo che soddisfa il problema è pertanto -310-7=-317.
Per cui tutti gli interi negativi che soddisfano il problema sono del tipo

$-317+330k\quad\quad \forall \;k\le 0 \in \aleph$

Ma ho il sospetto che ci sia una strada più semplice.

SE&O

Admin

P.S.: ho modificato più volte nelle ultime ore il post perchè mi sono accorto via via di vari errori; chiedo venia.

1)Essendo 17 primo e (12345, 17) coprìmi ,per il piccolo teorema
di Fermat (sempre lui!) si ha:
(1) $(12345)^{16} \equiv 1 (mod 17)$
Ora 12345=16*771+9 e quindi dalla (1) si deduce che :
(2) $(12345)^{12345} \equiv 12345^9 (mod 17)$
Ma e' pure 12345=726*17+3 e dunque:
(3) $12345^9 \equiv 3^9 (mod 17)$
(4) $3^9 \equiv 14 (mod 17)$
In definitiva da (2),(3),(4) si ricava che :
$(12345)^{12345} \equiv 14 mod (17)$
e pertanto il resto cercato e' 14
Leandro

...

Ottimi Pietro e Leandro!


Per Pietro

Tu hai scritto di aver qualche difficoltà con l'aritmetica modulare... io penso
invece che il tuo procedimento sia diretto, essenziale, e poi mi piace il fatto
che ti appassioni
Una sola piccola nota: il problema chiedeva i numeri naturali di tre cifre con
le caratteristiche indicate e quindi la risposta finale è 277, 607 e 937.
Ho tentato una via alternativa al secondo quiz e mi è saltato fuori questo.
Parto dal sistema:

$\{ x\equiv 7 \; (mod\, 10) \\ x\equiv 1 \; (mod\, 3) \\ x\equiv 2 \;(mod\, 11)$

e lo riduco allo stesso modulo (così posso sommare, sottrarre e moltiplicare):

$\{ 33x\equiv 231 \; (mod\, 330) \\ 110x\equiv 110 \; (mod\, 330) \\ 30x\equiv 60 \;(mod\, 330)$.

A questo punto, raddoppio i due membri della terza congruenza e la sommo
alla seconda e poi sottraggo il risultato dalla prima, arrivando a:

$-137x\equiv 1 \; (mod\, 330)$,

la quale equivale all'equazione diofantea lineare:

$1) \;\; -137x=330y+1$

che sappiamo risolvere in vari modi, ma di cui si può trovare una soluzione
con pochi adatti tentativi (osservando i coefficienti).
Quindi, trovo che:

$(x_0, \,y_0)=(-53, \, 22)$

è una soluzione della (1) e che tutte le $\,x\,$ hanno questa forma:

$x = -53+330t \,$ per qualunque $\,t\,$ intero.

I tre numeri cercati si ottengono per $\, t=1,2,3$.

Vabbè, questo è solo un intermezzo...


Sotto con l'altro, allora

3)
Si osserva che (07 sta per 7):
$7^1=(07),7^2=(49),7^3=3(43),7^4=24(01),7^5=168(07),7^6=1176(49),etc$
Si vede così che le potenze consecutive del 7 hanno,nelle ultime 2 cifre,un periodo di
ordine 4 e che naturalmente lo stesso avviene per i numeri che terminano con 07.
Periodo=07,49,43,01
Basta quindi dividere per 4 l'esponente 7447 (7447=4*1861+3) per stabilire
che le ultime 2 cifre richieste sono quelle relative al terzo passo del periodo
e cioe' 43
Salvo errori.
Leandro

...yesss

Ciao Bruno,
hai ragione, non ho letto con attenzione la traccia, per cui ho considerato tutti gli interi.

Le mie difficoltà sono legate all'applicazione dell'aritmetica modulare;
ad es. non mi è venuto in mente che i numeri che terminano per 7 corrispondono a $x\equiv 7\;(mod 10)$ ed ho scritto $10c+7$;
ad es. non avrei mai pensato a portare tutto allo stesso modulo.

In ogni caso ti ringrazio per i quiz, e se hai voglia e tempo per inviarne degli altri, sono ben accetti (ci sto prendendo gusto!).

Grazie anche a Leandro per le altre due soluzioni;
avevo abbozzato qualcosa...

A tal proposito ho aggiunto alcuni quesiti irrisolti della collezione, nel forum "irrisolti";
si tratta di quesiti appartenenti alla sezione "Aritmetica russa" e molti riguardano la divisibilità e le cifre terminali e penso possano essere risolti con l'aritmetica modulare.

qui i link al forum ed alla collezione:

https://www.base5forum.it/viewtopic.php?p=3408#3408
http://utenti.quipo.it/base5/numeri/aritrussa.htm

Ciao
Admin

Admin ha scritto:In ogni caso ti ringrazio per i quiz, e se hai voglia e tempo per inviarne degli altri, sono ben accetti (ci sto prendendo gusto!)

...contaci

Sai, il procedimento di Leandro (imbattibile ) per il terzo quiz potrebbe
suonare così con le note "congruenti".
Faccio tutti i passaggi, ma la cosa è più breve di come forse appare.
Sappiamo già che la ricerca del resto di $\, 7040407^{\small 7447}\,$ equivale a cercare
il resto di $\,7^{\small 7447}\,$.
Osservazioni preliminari (immediate):

$7^2=49\equiv-1 \; (mod \, 25) \; \to \; 7^4\equiv 1 \; (mod \, 25) \\ 49\equiv1 \; (mod \, 4) \; \to \; 7^4\equiv 1 \; (mod \, 4)$.

Una proprietà delle congruenze afferma che, se

$\{a\equiv b \; (mod \, r) \\ a\equiv b \; (mod \, s)$

allora, detto $\, [r,\,s]$ il minimo comune multiplo di $\, r \,$ ed $\, s$:

$a\equiv b \; (mod \, [r,\,s])$.

In questo caso abbiamo: $\;[25,\,4] =100 \;$ e quindi: $\;7^4\equiv 1 \; (mod \, 100)$.

Leandro ha già detto che 7447=4x1861+3, per cui abbiamo che:

$(7^4)^{1861}\equiv 1 \; (mod \, 100) \; \to \; 7^{7447}\equiv 7^3 \; (mod \, 100)$.

Le due utlime cifre richieste, pertanto, sono le stesse di $\, 7^3$.

Osserviamo subito che $\,7^3=(50-1)(10-3) = 500-160+3=300+43$
e nell'ultimo membro troviamo la risposta.

A presto!


Bruno

Bruno ha scritto:Sappiamo già che la ricerca del resto di $\, 7040407^{\small 7447}\,$ equivale a cercare
il resto di $\,7^{\small 7447}\,$

Ma ciò è vero solo $mod\, 100$.
O sbaglio?

Poi,

Bruno ha scritto:Parto dal sistema:

$\{ x\equiv 7 \; (mod\, 10) \\ x\equiv 1 \; (mod\, 3) \\ x\equiv 2 \;(mod\, 11)$

e lo riduco allo stesso modulo (così posso sommare, sottrarre e moltiplicare):

$\{ 33x\equiv 231 \; (mod\, 330) \\ 110x\equiv 110 \; (mod\, 330) \\ 30x\equiv 60 \;(mod\, 330)$

mi potresti spiegare meglio la riduzione allo stesso modulo?

Admin

Admin ha scritto:Ma ciò è vero solo $mod\, 100$. O sbaglio?

Yesss... sapendo che possiamo esprimere come segue una potenza binomiale:
$(a+b)^{\small n}=a\cdot k+b^{\small n} \,$ per un certo $\,k\,$.

Admin ha scritto: (...) mi potresti spiegare meglio la riduzione allo stesso modulo?

Subito.
Per far questo bisogna calcolare il minimo comune multiplo dei moduli e poi
moltiplicare i due membri di ciascuna congruenza per il rapporto fra il numero
trovato e il modulo originario di quella congruenza.
Le congruenze con lo stesso modulo possono essere sommate, sottratte
e moltiplicate membro a membro.

...

0 - Ouverture (facile facile): $\;$Il numero $\, 3\cdot (2n+1)^{\small 1648}+1 \,$, quando la lettera indichi
un numero pari, è divisibile per 4.

1) $\;$Risolvere ciascuna delle seguenti congruenze:

$10x\equiv 14 \;(mod \, 21) \\ 97x\equiv 13 \;(mod \, 105) \\ 12x \equiv 33 \; (mod \, 57) \\ 14x\equiv 1 \;(mod \, 77)$

e indicare, se esiste, la minima soluzione non negativa.

2) $\;$Trovare il resto di $\,(102^{\small 73}+55)^{\small 37}\,$ diviso per $\,111\,$.

3) $\;$Trovare il minimo resto non negativo di $\,13^{\small 216}\; (mod \, 19)$.

4) $\;$Qual è l'ultima cifra di $\,3^{\small 400}$ in base $\,12\,$?

5) $\;$ Trovare un naturale $\,r\,$ minore di $\,29\,$ tale che sia $\,17r\equiv 1\; (mod \, 29)$.

Ciao Bruno,
grazie mille per le risposte e per i nuovi quiz.
Provo appena posso!

Ciao
Admin

0 - Ouverture

$n$ pari significa $n\equiv 0 (mod\, 2)$ da cui $2n \equiv 0 (mod 4)$; da cui:

$2n+1 \equiv 1 (mod\, 4)$
$(2n+1)^{1648} \equiv 1^{1648} (mod\, 4) \quad\Rightarrow\quad (2n+1)^{1648} \equiv 1 (mod\, 4)$
$3\cdot(2n+1)^{1648} \equiv 3\cdot1 (mod\, 4)$
$3\cdot(2n+1)^{1648}+1 \equiv 3\cdot1+1 (mod\, 4) \quad\Rightarrow\quad 3\cdot(2n+1)^{1648}+1 \equiv 4 (mod\, 4) \quad\Rightarrow\quad 3\cdot(2n+1)^{1648}+1 \equiv 0 (mod\, 4)$

Admin

1)

• $10x \equiv 14 (mod\, 21)$
  
  possiamo avere valori di $x$ interi positivi e negativi;
  nel caso dei positivi la congruenza corrisponde all'equazione lineare
  $10x=21y+14$ da cui si nota che il minimo valore di $y$ tale che $x$ sia positivo ed intero è $6$.
  Sostituendo si ottiene $10x=21\cdot6+14 \quad\Rightarrow\quad x=14$
  per cui le soluzioni positive della congruenza sono del tipo
  $x=14+21k \quad\quad \forall k \in N : k\ge 0$
  per i negativi la congruenza corrisponde a
  $10x=-21y-7$ (il resto negativo che si deve avere è infatti -7=14-21)
  il minimo valore di y che ci da un x intero negativo è 3, per cui
  $10x=-21\cdot 3-7 \quad\Rightarrow\quad x=-7$
  per cui le soluzioni negative della congruenza sono del tipo
  $x=-7-21k \quad\quad\forall k \in N : k\ge 0$

Admin

...scatenato
Vai Pietro!