« “L’imitació” és millor que l’original
Els nostres cervells tenen estructura de Lògica de Primer Ordre? »

mcd(0,a)=….

24th Juny 2008, 04:24 pm

L’altre dia llegint un llibre, vaig veure aquest que definia el mcd(a,b) com “el màxim comú divisor estrictament positiu de a i de b si a i b eren tots dos distints de zero i 0 altrament”.

Me va sorprendre aquesta definició i vaig intentar justificar-la (òbviament el cas que algun dels arguments fos zero) de dues maneres:

1. Amb la definició de divisor comú

Donats a, b\in \mathbb{Z}, podem definir que c és un divisor comú de a i de b \Leftrightarrow c és un divisor de a i c és un divisor de b simultàniament, i.e. a = c \cdot e i b = c \cdot f per alguns e, f \in \mathbb{Z}(nota: aquesta és la definició més general de divisor. Hi ha altres definicions que exigeixen que c sigui distint de zero, per a què el concepte de divisor en la divisor entera i aquest concepte coincideixin. Ara bé, si elegim que c sigui distint de zero, aleshores no hi ha una correspondència entre múltiples i divisors d’un nombre).

Per tant, tenim que donats, a, b sencers, podem definir el conjunt de divisors de a i b com

\text{Div}(a,b) =\{ c \text{ divisor com\'u de } a \text{ i } b\}

I per tant, definir el màxim comú divisor de a i de b com:

\text{mcd}(a,b) = \max \text{Div}(a,b)

Aleshores si a no és zero, el mcd(a,0) és igual a

\text{mcd}(a,0) = \max \text{Div}(a,0) = \max (\text{Div}(a) \cap \text{Div}(0)) = \max (\text{Div}(a) \cap \mathbb{Z}) = a

(ja que qualsevol nombre és divisor de zero)

i

\text{mcd}(0,0) = \max \text{Div}(0,0) = \max (\text{Div}(0) \cap \text{Div}(0)) = \max (\mathbb{Z} \cap \mathbb{Z}) = \max \mathbb{Z} que no existeix

Per tant, amb una definició raonable del mcd, arribem a la conclusió de què mcd(0,a) = a si a no és zero i que mcd(0,0) no existeix.

2. Amb un poc d’àlgebra (ideals amagats)

Ara bé, facem servir un poc d’Àlgebra.

Notem per (a) = \{ m | \text{m\'ultiples de a}\} = \{0, a, -a, \ldots \} = \{k\cdot a | k \in \mathbb{Z}\} ,  i de forma més general

(a_1, \ldots, a_r) = \{k_1 \cdot a_1 + \ldots k_r \cdot a_r | k_i \in \mathbb{Z}\}

O sigui (a_1, \ldots, a_r) és l’ideal general pel conjunt \{a_1, \ldots, a_r\} a \mathbb{Z}

Es pot veure que donats a, b enters, tenim que:

  • (a, b) = (\text{mcd}(a,b))
  • (a) \cap (b) =(\text{mcm}(a,b))

Si b =0 i a no és zero, tenim que (a, 0) = (a). Per tant, el mcd(0,a) hauria de ser a.

Si a i b són zero, llavors, (0,0) = {0} = (0). Per tant, el mcd(0,0) hauria de ser 0.

Conclusions

Aleshores, amb tot, trec que:

  1. una bona definició per  mcd(0,a) seria a
  2. una bona definició per mcd(0,0) seria 0
  3. El llibre “s’equivocava”: de totes totes el mcd(0,a) no és zero (tenc dos arguments per demostrar divergències amb aquesta definició).

Algú més s’atreveix a donar un altra argument? Per favor, animeu-vos!

Categoria: problemes, llibres, reflexions, matemàtiques  |  Comentari (RSS)  |  Retroenllaç

4 comentaris

  1. Félix:

    Hola Xavi. A nivell molt elemental (parlem de sentit comú, amb el perill que això suposa) estic d’acord amb que MCD(a,0) = a i que MCD(0,0) no existeix.
    Revisant els teus raonaments m’ha sorgit un dubte. Al raonament algebraic, no defineixes el MCD. Quina definició empres quan dius (a,b)=(mcd(a,b))? I per altra banda, si empram la definició que utilitzes al raonament aritmètic (1 per entendre’ns) hi ha una degeneració a qualque banda perquè no pot ser que per un raonament ens doni que no existeix el MCD(0,0) i per altra banda que sigui 0. Pot ser interessant estudiar en quin punt es degenera el procés i per què.
    Una altra cosa, al raonament (1) diu
    a = c · e i a = c · f
    i si no m’equivoc hauria de dir
    a = c · e i b = c · f
    Finalment, em deman si a part de la curiositat de com definir MCD(0,0) podem trobar qualque problema on sorgeixi la necessitat d’utilitzar això.
    Salutacions,
    Félix.

    24 Juny 2008, 5:41 pm

  2. Xavi:

    Félix: el de a i b ja està corregit.
    Sí, és cert que no defineix el mcd: algebraicament diríem que _un_ màxim comú divisor seria un nombre d tal que (a, b) = (d). I _el_ màxim comú divisor seria un nombre tal que a més for >= 0.

    Sobre la degeneració que dius, no estic gaire d’acord. Encara que les definicions hauríen de coincidir no tendria per què, per què les definicions de partida, i els conceptes de partida són distints. és clar que s’han d’armonitzar però podria ser que els conceptes de partida donassin definicions distintes….. ara bé, no crec que en aquest cas passàs perquè la def. algebraica històricament ve de l’altra.

    A veure si trobes l’error doncs.
    Xavi

    24 Juny 2008, 6:53 pm

  3. defaultcesc:

    Hola,
    d’entrada tens rao, Xavi: mcd(a,0)=a si a no es 0, devia ser una errata del llibre.

    El que sol fer quan se és molt esquiterell (i de vegades cal ser-ho; de fet, qui ho introduí és Paul Erdös) és distingir entre maxim comu divisor mcd i divisor en comu distingit dcd (idem per als multiples): el primer és el major element (respecte de l’ordre usual) del conjunt dels divisors en comú, el segon, el (llevat de signe) major element (respecte de l’ordre parcial “x més gran que y si y divideix x”) del conjunt dels divisors en comú. I com be has observat

    mcd(a,b)=dcd(a,b) si qualcun no és 0

    dcd(0,0)=0, mcd(0,0) no existeix.

    28 Juny 2008, 8:40 am

  4. defaultXavi:

    Xesc, en primer lloc suposo que “esquiterell”=primmirat! (?)
    En segon lloc, gràcies per la reflexió.
    Ara sabem més de l’assumpte.

    Per tant, deduesc que (a) \cap (b) = (dcd(a,b))?

    Gràcies pels comentaris.
    Xavi

    29 Juny 2008, 11:00 am

Deixa un comentari