• Non ci sono risultati.

EQUAZIONI LINEARI DIOFANTEE

N/A
N/A
Info
Scarica
Protected

Academic year: 2022

Condividi "EQUAZIONI LINEARI DIOFANTEE"

Copied!
18
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 18 pagine )

Testo completo

(1)

EQUAZIONI LINEARI DIOFANTEE

Le equazioni del tipo π‘Žπ‘₯ + 𝑏𝑦 = 𝑐

si chiamano equazioni lineari diofantee Le incognite sono π‘₯, 𝑦 𝑒 π‘ π‘œπ‘›π‘œ 𝑖𝑛 𝑍

Esempio: 6π‘₯ + 7𝑦 = 9

(2)

Le equazioni lineari diofantee π‘Žπ‘₯ + 𝑏𝑦 = 𝑐

possono essere di due tipi

1) c = 0 ( π‘Ž, 𝑏 β‰  0) 2) c β‰  0 ( π‘Ž, 𝑏 β‰  0)

1)

Nel primo caso si ha 𝒂𝒙 + π’ƒπ’š = 𝟎 E poniamo 𝒙 = 𝒃𝒕 con t in Z Allora 𝑑𝑒𝑣𝑒 π‘’π‘ π‘ π‘’π‘Ÿπ‘’ π‘π‘’π‘Ÿ π‘“π‘œπ‘Ÿπ‘§π‘Ž π’š = βˆ’ 𝒂𝒃

𝒃 𝒕 ( π‘π‘œπ‘ π‘ π‘–π‘π‘–π‘™π‘’ π‘π‘’π‘Ÿπ‘β„ŽΓ¨ 𝑏 β‰  0 ) π‘œπ‘£π‘£π‘’π‘Ÿπ‘œ π’š = βˆ’π’‚π’•

(3)

PROVA

Dimostrare che

π‘₯ = 𝑠 e 𝑦 = π‘Ÿ

Γ¨ una coppia di soluzioni di π‘Žπ‘₯ + 𝑏𝑦 = 0 vuol dire dimostrare che

Β«sostituendo questi valori nell’equazione si ha un’identitΓ  ovvero un’uguaglianza sempre veraΒ»

OSS: Β«Sempre Γ¨ un avverbio di tempo: in italiano vuol dire per ogni istante ma in matematica vuol dire per ogni valore delle incogniteΒ»

Quindi vuol dire dimostrare che

a*(valore ipotizzato) + b*(valore ipotizzato ) = 0 Γ¨ una affermazione sempre vera ( veritΓ  ) Nel nostro caso abbiamo

π‘₯ = 𝑏𝑑 e 𝑦 = βˆ’π‘Žπ‘‘ Quindi dobbiamo dimostrare che

π‘Ž βˆ— 𝑏𝑑 + 𝑏 βˆ— βˆ’π‘Žπ‘‘ = 0 Γ¨ una cosa vera

(4)

Quindi dobbiamo dimostrare che

π‘Ž βˆ— 𝑏𝑑 + 𝑏 βˆ— βˆ’π‘Žπ‘‘ = 0 Γ¨ una cosa vera Eseguiamo i calcoli indicati a sinistra quindi

π‘Ž βˆ— 𝑏𝑑 + 𝑏 βˆ— βˆ’π‘Žπ‘‘ = 0 equivale a π‘Ž βˆ— 𝑏𝑑 βˆ’ π‘Ž βˆ— 𝑏𝑑 = 0 che equivale a

0 = 0 che Γ¨ una veritΓ 

Quindi π‘Ž βˆ— 𝑏𝑑 + 𝑏 βˆ— βˆ’π‘Žπ‘‘ = 0 Γ¨ una cosa vera

Quindi π‘₯ = 𝑏𝑑 e 𝑦 = βˆ’π‘Žπ‘‘ Γ¨ una coppia di soluzioni di π‘Žπ‘₯ + 𝑏𝑦 = 0 con 𝑑 ∈ 𝑍

(5)

Dette

A = Β« x = s Β» B = Β« y = r Β» e C = Β« π‘Žπ‘₯ + 𝑏𝑦 = 0Β» e

Β« A ∧ 𝑩 ∧ π‘ͺ Β» la loro congiunzione Dire che

𝒙 = 𝒔 e π’š = 𝒓 Γ¨ 𝒖𝒏𝒂 coppia di soluzioni di 𝒂𝒙 + π’ƒπ’š = 𝟎 equivale a dire che

Β« A ∧ 𝑩 ∧ π‘ͺΒ» Γ¨ vera

Ovvero equivale ad enunciare una CONTEMPORANEITÀ VERA di eventi e si può scrivere anche così

ቐ

𝒙 = 𝒔 π’š = 𝒓

𝒂𝒙 + π’ƒπ’š = 𝟎

(6)

Quindi data π‘Žπ‘₯ + 𝑏𝑦 = 0 π‘žπ‘’π‘’π‘ π‘‘π‘Ž β„Žπ‘Ž π‘π‘’π‘Ÿ π‘ π‘œπ‘™π‘’π‘§π‘–π‘œπ‘›π‘’ π‘™π‘Ž π‘π‘œπ‘π‘π‘–π‘Ž [𝑏𝑑 ;βˆ’π‘Žπ‘‘] con 𝑑 ∈ 𝑍

Esempio:

data 5x+8y=0 essa ha per soluzione la coppia (8t; -5t) con t∈ 𝑍 Ovvero l’insieme delle infinite coppie (8t; -5t) al variare di t in Z Quindi

per t=1 (8,-5)

per t=-2 (-16,10)

E via di seguito

(7)

ESERCIZI

Date le equazioni 4π‘₯ βˆ’ 6𝑦 = 0 e 3π‘₯ + 8𝑦 = 0

Per ognuna di esse indica la coppia 𝑏𝑑, βˆ’π‘Žπ‘‘ soluzione

e successivamente trova alcune coppie appartenenti

all’insieme delle coppie 𝑏𝑑, βˆ’π‘Žπ‘‘ al variare di t in Z

(8)

Quindi data l’equazione π‘Žπ‘₯ + 𝑏𝑦 = 0 essa ha per soluzione tutte le coppie 𝑏𝑑, βˆ’π‘Žπ‘‘

2) c≠ 0

Nel secondo caso vale il seguente teorema che non dimostriamo:

TEOREMA

Β«L’equazione π‘Žπ‘₯ + 𝑏𝑦 = 𝑐 ha soluzioni in Z se e solo se

MCD (a,b ) divide cΒ»

(9)

Esempio:

21π‘₯ + 15𝑦 = 14 β„Žπ‘Ž π‘ π‘œπ‘™π‘’π‘§π‘–π‘œπ‘›π‘– 𝑖𝑛 𝑍?

Il teorema prima enunciato dice che la suddetta equazione ha soluzioni se

14 divide il M.C.D. tra 21 e 15, ma il M.C.D. (21,15) Γ¨ 3

e 3 non divide 14

Invece l'equazione 21π‘₯ + 15𝑦 = 6 ha soluzioni in Z perchΓ© il

𝑀. 𝐢. 𝐷. (21,15) = 3 e 3 divide 6

(10)

Come possiamo trovare le soluzioni di 21π‘₯ + 15𝑦 = 6?

Per l’idenditΓ  di Bezout noi sappiamo che esistono h e k tali che 3 = 21β„Ž + 15π‘˜

Che Γ¨ la stessa cosa che dire che esistono x e y tali che 3 = 21π‘₯ + 15𝑦 Andiamo intanto a trovare questi due valori con l’algoritmo euclideo

21: 15 = 1 π‘π‘œπ‘™ π‘Ÿπ‘’π‘ π‘‘π‘œ 𝑑𝑖 6 π‘žπ‘’π‘–π‘›π‘‘π‘– 21 = 1 βˆ— 15 + 6 π‘žπ‘’π‘–π‘›π‘‘π‘– 6 = 21 βˆ’ 15 βˆ— 1 15: 6 = 2 π‘π‘œπ‘™ π‘Ÿπ‘’π‘ π‘‘π‘œ 𝑑𝑖 3 π‘žπ‘’π‘–π‘›π‘‘π‘– 15 = 6 βˆ— 2 + 3π‘žπ‘’π‘–π‘›π‘‘π‘– 3 = 15 βˆ’ 6 βˆ— 2

6: 3 = 2 π‘π‘œπ‘™ π‘Ÿπ‘’π‘ π‘‘π‘œ 𝑑𝑖 π‘§π‘’π‘Ÿπ‘œ π‘žπ‘’π‘–π‘›π‘‘π‘– 𝑀. 𝐢. 𝐷. 21,15 = 3

(11)

π‘…π‘–π‘π‘Ÿπ‘’π‘›π‘‘π‘–π‘Žπ‘šπ‘œ π‘‘π‘Ž 𝑀. 𝐢. 𝐷. 21,15 = 3

𝑒 π‘‘π‘Žπ‘™π‘™

β€²

π‘’π‘”π‘’π‘Žπ‘”π‘™π‘–π‘Žπ‘›π‘§π‘Ž π‘β„Žπ‘’ π‘’π‘ π‘π‘Ÿπ‘–π‘šπ‘’ 3 ( π‘Ÿπ‘œπ‘ π‘ π‘Ž ) Quindi 3 = 15 βˆ’ 6 βˆ— 2 𝑒 π‘ π‘œπ‘ π‘‘π‘–π‘‘π‘’π‘’π‘›π‘‘π‘œ π‘™π‘Ž π‘£π‘’π‘Ÿπ‘‘π‘’

π‘‘π‘–π‘£π‘’π‘›π‘‘π‘Ž 3 = 15 βˆ’ 21 βˆ’ 15 βˆ— 1 βˆ— 2

𝑒 π‘‘π‘–π‘£π‘’π‘›π‘‘π‘Ž 3 = 15 βˆ’ 21 βˆ— 2 + 15 βˆ— 2 𝑒 π‘‘π‘–π‘£π‘’π‘›π‘‘π‘Ž 3 = βˆ’21 βˆ— 2 + 15 βˆ— 3 π‘œπ‘£π‘£π‘’π‘Ÿπ‘œ

3 = βˆ’2 βˆ— 21 + 15 βˆ— 3

E quindi i due numeri cercati sono π‘₯ = βˆ’2 𝑒 𝑦 = 3

(12)

[ OSS.: se A=B allora 2A=2B, 3A=3B,….]

[ovvero moltiplicando a sinistra e a destra un’uguaglianza per lo spesso fattore l’uguaglianza non cambia ]

Quindi se vale 3 = βˆ’21 βˆ— 2 + 15 βˆ— 3

Allora vale anche l’uguaglianza che si ottiene

moltiplicando a sinistra e a destra per 2 ovvero la precedente uguaglianza 3 βˆ— 2 = βˆ’21 βˆ— 2 + 15 βˆ— 3 βˆ— 2 ovvero

6 = βˆ’21 βˆ— 2 βˆ— 2 + 15 βˆ— 3 βˆ— 2

che possiamo scrivere anche nel seguente modo avendo cura di lasciare i fattori 21 e 15 che ci servono

6 = βˆ’21 βˆ— 4 + 15 βˆ— 6

Quindi abbiamo trovato x e y tali che 21π‘₯ + 5𝑦 = 6 ovvero π‘₯ = βˆ’4 𝑒 𝑦 = 6

(13)

Quindi l’equazione π‘Žπ‘₯ + 𝑏𝑦 = 𝑐

ha soluzioni se e solo se 𝑑 = 𝑀. 𝐢. 𝐷. (π‘Ž, 𝑏) divide c ( TEOREMA ) e ha per soluzioni:

π‘₯ = β„Ž βˆ— (𝑐: 𝑑) 𝑒 𝑦 = π‘˜ βˆ— (𝑐: 𝑑)

Dove h e k sono i numeri in Z dell’identitΓ  di Bezout Ovvero

𝑑 = π‘Ž βˆ— β„Ž + 𝑏 βˆ— π‘˜

(14)

Quindi l’equazione π‘Žπ‘₯ + 𝑏𝑦 = 𝑐

ha soluzioni se e solo se 𝑑 = 𝑀. 𝐢. 𝐷. (π‘Ž, 𝑏) divide c ( TEOREMA )

E, per trovare la coppia di soluzioni, bisogna procedere nel seguente modo:

π‘‡π‘Ÿπ‘œπ‘£π‘œ 𝑑 = 𝑀. 𝐢. 𝐷. π‘Ž, 𝑏 𝑒 π‘£π‘’π‘‘π‘œ 𝑠𝑒 𝑑 𝑑𝑖𝑣𝑖𝑑𝑒 𝑐

Costruisco 𝑙′𝑖𝑑𝑒𝑛𝑑𝑖𝑑à 𝑑𝑖 π΅π‘’π‘§π‘œπ‘’π‘‘ π‘π‘œπ‘› π‘™β€²π‘Žπ‘™π‘”π‘œπ‘Ÿπ‘–π‘‘π‘šπ‘œ π‘’π‘’π‘π‘™π‘–π‘‘π‘’π‘œ Ovvero π‘‘π‘Ÿπ‘œπ‘£π‘œ β„Ž 𝑒 π‘˜ π‘‘π‘Žπ‘™π‘– π‘β„Žπ‘’ 𝑑 = π‘Ž βˆ— β„Ž + 𝑏 βˆ— π‘˜

A questo punto calcolo x e y con le seguenti formule

π‘₯ = β„Ž βˆ— (𝑐: 𝑑) 𝑒 𝑦 = π‘˜ βˆ— (𝑐: 𝑑)

Se vuoi prima calcoli 𝑐: 𝑑 = π‘š e poi applichi le formule π‘₯ = β„Ž βˆ— π‘š 𝑒 𝑦 = π‘˜ βˆ— π‘š

(15)

𝐸𝑆𝐸𝑀𝑃𝐼𝑂

Risolvi in Z : 56π‘₯ + 21𝑦 = 35 [a=56; b=21; c=35]

RICORDA: ha soluzioni se e solo se d = 𝑀. 𝐢. 𝐷. (π‘Ž, 𝑏) divide c ( TEOREMA ) π‘‡π‘Ÿπ‘œπ‘£π‘œ 𝑀. 𝐢. 𝐷. 56; 21 : 7 𝑑𝑖𝑣𝑖𝑑𝑒 35 𝑐 ? 𝑆𝐼

Costruisco 𝑙′𝑖𝑑𝑒𝑛𝑑𝑖𝑑à 𝑑𝑖 π΅π‘’π‘§π‘œπ‘’π‘‘ π‘π‘œπ‘› π‘™β€²π‘Žπ‘™π‘”π‘œπ‘Ÿπ‘–π‘‘π‘šπ‘œ π‘’π‘’π‘π‘™π‘–π‘‘π‘’π‘œ Ovvero π‘‘π‘Ÿπ‘œπ‘£π‘œ β„Ž 𝑒 π‘˜ π‘‘π‘Žπ‘™π‘– π‘β„Žπ‘’ 7 = 56β„Ž + 21π‘˜

Per poi usare le formule

π‘₯ = β„Ž βˆ— (𝑐: 𝑑) 𝑒 𝑦 = π‘˜ βˆ— (𝑐: 𝑑)

(16)

Tπ‘Ÿπ‘œπ‘£π‘œ β„Ž 𝑒 π‘˜ π‘‘π‘Žπ‘™π‘– π‘β„Žπ‘’ 7 = 56β„Ž + 21π‘˜

56: 21 = 2 π‘π‘œπ‘™ π‘Ÿπ‘’π‘ π‘‘π‘œ 𝑑𝑖 14 π‘žπ‘’π‘–π‘›π‘‘π‘– 56 = 21 βˆ— 2 + 14 π‘žπ‘’π‘–π‘›π‘‘π‘– 14 = 56 βˆ’ 21 βˆ— 2 21: 14 = 1 π‘π‘œπ‘™ π‘Ÿπ‘’π‘ π‘‘π‘œ 𝑑𝑖 7 π‘žπ‘’π‘–π‘›π‘‘π‘– 21 = 14 βˆ— 1 + 7 π‘žπ‘’π‘–π‘›π‘‘π‘– 7 = 21 βˆ’ 14 βˆ— 1

14: 7 = 2 π‘π‘œπ‘™ π‘Ÿπ‘’π‘ π‘‘π‘œ 0

Quindi il M.C.D. Γ¨ 7 e quindi riparto dall’uguaglianza (rossa) che ha a sinistra 7 Ovvero 7 = 21 βˆ’ 14 βˆ— 1

sostiuisco 14 (verde) e ottengo 7 = 21 βˆ’ (56 βˆ’ 21 βˆ— 2) βˆ— 1 che equivale a

7 = 21 βˆ’ 56 βˆ— 1 + 21 βˆ— 2 βˆ— 1 che equivale a

7 = 21 βˆ’ 56 βˆ— 1 βˆ’ 21 βˆ— 2 π‘β„Žπ‘’ π‘’π‘žπ‘’π‘–π‘£π‘Žπ‘™π‘’ π‘Ž 7 = 21 βˆ— 3 βˆ’ 56 βˆ— 1

(17)

Quindi ho costruito l’indentitΓ  di Bezout per 56 e 21 ovvero 7 = 21 βˆ— 3 βˆ’ 56 βˆ— 1

Quindi ho trovato h e k tali che 7 = 56β„Ž + 21π‘˜ ovvero β„Ž = βˆ’1 𝑒 π‘˜ = 3

Quindi trovo x e y soluzioni di 56π‘₯ + 21𝑦 = 35

con le formule π‘₯ = β„Ž βˆ— (𝑐: 𝑑) 𝑒 𝑦 = π‘˜ βˆ— (𝑐: 𝑑) Ovvero

π‘₯ = βˆ’1 βˆ— 35: 7 = βˆ’5 𝑒 𝑦 = 3 βˆ— 35: 7 = 15 PROVA

56 βˆ— βˆ’5 + 21 βˆ— 15 = 35 π‘’π‘žπ‘’π‘–π‘£π‘Žπ‘™π‘’ π‘Ž

βˆ’280 + 315 = 35 π‘β„Žπ‘’ π‘’π‘žπ‘’π‘–π‘£π‘Žπ‘™π‘’ π‘Ž 0 = 0

(18)

𝐸𝑆𝐸𝑅𝐢𝐼𝑍𝐼

Trova le soluzioni in Z di:

4π‘₯ + 22𝑦 = 10 18π‘₯ βˆ’ 27𝑦 = 5 18π‘₯ βˆ’ 27𝑦 = 36

31π‘₯ + 47𝑦 = 1

Riferimenti

Scarica adesso ( PDF - 18 pagine - 364.66 KB )

Documenti correlati

sistemi di equazioni lineari

G45:g.01 Le caratteristiche di risolubilit` a di un sistema di equazioni lineari, cio` e l’esistenza di una soluzione, di infinite soluzioni o la assenza di soluzioni, sono chiarite

Sistemi di equazioni lineari

[r]

Teorema delle successioni monotone Enunciato

Per semplicit`a dimostreremo che ogni successione di di numeri reali i) non decrescente e ii) limitata superiormente `e

Teorema di Fermat Enunciato Ipotesi

Dimostrazione Supponiamo, per fissare le idee, che x 0 sia un punto di

Teorema di integrabilit`a delle funzioni continue Enunciato Sia f ∈ C

Osserviamo che la lunghezza di ogni subintervallo risulta essere (bβˆ’a)/n

Equazioni differenziali lineari

Possono avere precisioni diverse: i pi` u comuni sono esatti fino al secondo e

Sistemi di equazioni lineari a

Si vede con la pratica che l’eliminazione gaus- siana ` e molto pi` u stabile se gli elementi di ma- trice sulla diagonale principale sono pi` u grandi degli altri in valore

Equazioni differenziali lineari

Possono avere precisioni diverse: i pi` u comuni sono esatti fino al secondo e quarto ordine.. Si pu` o procedere con ordini superiori al secondo.. , z N ).. Le regole di