Sulle congruenze

[domx]

Ciao a tutti, perdonate la mia stupida domanda, ma non riesco a capire come fanno i testi a dire che in una congruenza dove a è congruo a b modulo n (non riesco a scriverlo col latex) a e b, se divisi per n, danno lo stesso resto. Nel caso in cui -14 è congruo ad 1 modulo 5, -14/5 dà 2 con resto 4, 1/5 dà 0 con resto 1. Mi chiarireste questo dubbio?
Ciao e grazie

[staffo]

$ -14:5 $ da $ -2 $, ma con resto $ -4 $, e poichè $ -4 $ è congruo a $ 1 $, segue che $ -14 $ è congruo ad $ 1 $.

[domx]

$ -14:5 $ da $ -2 $, ma con resto $ -4 $, e poichè $ -4 $ è congruo a $ 1 $, segue che $ -14 $ è congruo ad $ 1 $.

ma dici facendo a-b? Perché il resto però è diverso...

[staffo]

Nelle congruenze tu non hai delle uguaglianze, ma appunto delle congruenze. Dire resto -4 o dire resto 1 è la stessa cosa (mod5). questo perchè devi valutarlo rispetto a 5: resto -4 significa che mancano 4 unità per arrivare a 5 e multipli, resto 1 significa che hai 1 in più d un multiplo di 5, e quindi ti mancano 4 ad arrivare a 5 o multipli.

[domx]

Nelle congruenze tu non hai delle uguaglianze, ma appunto delle congruenze. Dire resto -4 o dire resto 1 è la stessa cosa (mod5). questo perchè devi valutarlo rispetto a 5: resto -4 significa che mancano 4 unità per arrivare a 5 e multipli, resto 1 significa che hai 1 in più d un multiplo di 5, e quindi ti mancano 4 ad arrivare a 5 o multipli.

ah, ho capito, però i testi questo dovrebbero spiegarlo...
comunque non capisco dove si possano applicare le congruenze nelle olimpiadi di matematica, almeno nelle provinciali (i risultati tra l'altro non le nominano mai)...

[Il_Russo]

a è congruo a b modulo n (non riesco a scriverlo col latex)

Codice: Seleziona tutto

a \equiv b \pmod{n}

$a \equiv b \pmod{n}$

Per quanto riguarda la domanda, il resto, di solito, si suppone tra $0$ e $n-1$. Quindi $-14 = -3 \cdot 5 + 1$; il quoziente è $-3$ ed il resto è $1$, come previsto. Poi a volte, come rappresentanti delle classi di resto, conviene usare numeri negativi, ad esempio $-1$ invece di $n-1$, perché i calcoli sono più semplici. Nota che $n-1 - (-1) = n$, definizione di congruenza; e che $-1 = -1 \cdot n + (n-1)$, definizione di divisione euclidea.

[domx]

sì ora ho capito, grazie ad entrambi
però mi continuo a domandare come si possano usare nelle olimpiadi...

[Il_Russo]

Sono sicurissimo che negli scorsi febbrai si usassero. Controlla meglio.

[domx]

Sono sicurissimo che negli scorsi febbrai si usavano. Controlla meglio.

ok, ora magari cerco in rete...

[LukasEta]

Guarda, probabilmente tu risolvendo i problemi usi spessissimo il concetto di congruenza, senza rendertene conto Già quando ragioni sui numeri pari-dispari stai in realtà parlando di congruenze modulo 2.. Ti faccio alcuni esempi di esercizi di febbraio passati, dove usando le congruenze ti riduci enormemente il lavoro:

FEBBRAIO 2007 (problema 2)
Un mercante ha 6 barili di capacità 15, 16, 18, 19, 20 e 31 litri. Cinque di essi sono pieni di vino e solo uno di essi `e pieno di birra. Il mercante tiene per se il barile di birra e vende tutti i barili di vino a due persone diverse, senza frazionarne il contenuto. Se uno dei due acquirenti ha comprato una quantità di vino esattamente doppia di quella acquistata dall’altro, quanti litri contiene il barile di birra?

Bè intanto si arriva facilmente a dire che se vende 2 parti a uno, e 1 parte all'altro, allora la quantità totale di vino venduta sarà divisibile per 3. Ciò significa anche che sommando tra loro 5 tra i 6 numeri corrispondenti alle capacità dei barili,se riesci a trovarne 5 che sommati danno un numero divisibile per 3, hai vinto, perchè il barile restante sarà quello di birra. Ora tu potresti cominciare a prenderne 5 a caso e sommarli, sperando che venga divisibile per 3...certamente continuando così alla fine troveresti la soluzione , ma perderesti un sacco di tempo su un problema che richiede meno di un minuto: ragioniamo infatti "modulo 3": cosa vuol dire? che la somma dei 5 barili venduti deve essere congrua a 0 modulo 3.

Per schematizzare le cose,scriviamo il resto della divisione per 3 del volume dei 6 barili:
15 ----> resto 0 (o anche 15$ \equiv 0 $) mod 3
16 ----> resto 1
18 -----> resto 0
19 ----> resto 1
20 ----> resto 2
31 --->resto 1

Se sommiamo tra loro i resti, otteniamo il resto della somma dei 6 volumi quando la dividiamo per 3 : 0+1+0+1+2+1 $ \equiv $5 $ \equiv $2 $ \mod 3 $
Se quindi togliamo un barile che ha un volume che dà resto 2 , allora quello che resta sarà congruo a 0 mod 3. L'unico barile che dà resto è quello da 20, che è quindi il barile di birra.
Molto più lungo dirlo che farlo, fidati

Analogamente , prova ad applicare lo stesso principio qui:

FEBBRAIO 2010
In quanti modi diversi si possono mettere in fila i numeri
{21, 31, 41, 51, 61, 71, 81} in modo che,
comunque se ne scelgano quattro in posti consecutivi, la loro somma sia divisibile per tre?

Divisibile per 3 eh...mmm...puzza di congruenze modulo 3 non trovi?

[domx]

Grazie mille LukazEta, sei stato chiarissimo, io quello sui barili lo feci in almeno 5-10 minuti l'altro giorno, facendo tutte le somme a mano
Allora, ci provo con l'altro: innanzitutto noto che per il criterio di divisibilità per 3, posso sommare le cifre e trasformare i numeri in:
{3; 4; 5; 6; 7; 8; 9}
e qui ci ero arrivato proprio ieri applicando, inconsapevolmente, il concetto di congruenze.
Noi quindi vogliamo disporre questi numeri in modo che la somma di quattro presi a caso sia congruente con zero modulo 3, giusto?
Allora, ecco a cosa sono congruenti modulo tre:
$ 3 \equiv 0 \pmod{3} $
$ 4 \equiv 1 \pmod{3} $
$ 5 \equiv 2 \pmod{3} $
$ 6 \equiv 0 \pmod{3} $
$ 7 \equiv 1 \pmod{3} $
$ 8 \equiv 2 \pmod{3} $
$ 9 \equiv 0 \pmod{3} $
quindi questi quattro numeri dovranno essere necessariamente due presi tra 3, 6 e 9, uno preso tra 4 e 7 ed uno preso tra 5 ed 8.
Il problema ora è che non riesco a trovare un ordine per disporli, se faccio in modo che il primo, secondo, terzo e quarto rispettino la richiesta, questo non vale per il secondo, terzo, quarto e quinto o per quelli dal terzo al sesto... mi aiuti?
comunque avevi ragione, le congruenze le usavo già inconsapevolmente, ma da ora starò più attento ad individuarle