Aritmètica modular

Archiu:Disqvisitiones-800.jpg

Coberta de l'edició original de Disquisitiones arithmeticae de Gauss, llibre fonamental de l'aritmètica modular.

En matemàtica, precisament en teoria de números; la aritmètica modular és un conjunt de métodos que permeten la resolució de problemes sobre número entero. Estos métodos deriven de l'estudi del restant obtingut per mig d'una divisió euclídea. Va ser introduïda en 1801 per Carl Friedrich Gauss en el seu llibre Disquisitiones Arithmeticae.

Un us familiar de la aritmètica modular és en el rellonge de 12 hores, en el que el dia es dividix en dos periodos de 12 hores. Si l'hora és a les 7:00, llavors 8 hores més vesprada seran les 3:00. L'adició simple donaria com a resultat 7 + 8 = 15, pero a les 15:00 es llig com 3:00 en l'esfera del rellonge perque els rellonges "s'envolen" cada 12 hores i el número d'hora comença de nou en zero quan aplega a les 12. Diem que 15 és congruent en 3 mòdul 12, escrit $15\equiv 3(mod12)$, de modo que $7+8\equiv 3(mod12)$. De la mateixa manera, les 8:00 representa un periodo de 8 hores, i el doble d'açò donaria 16:00, que es llig com 4:00 en l'esfera del rellonge, escrit com $2\cdot 8\equiv 4(mod12)$.

Relació de congruència

Archiu:Clock group.svg

El temps dut per este rellonge usa aritmètica en mòdul 12.

L'aritmètica modular pot ser construïda matemàticament per mig de la relació de congruència entre sancers, que és compatible en les operacions en l'anelle de sancers: suma i multiplicació. Per a un determinat mòdul $n$, esta es definix de la següent manera:

Esta relació es pot expressar cómodament utilisant la notació de Gauss:

$a\equiv b(modn)$

Aixina es té per eixemple:

$63\equiv 83(mod10)$

ya que abdós, 63 i 83 deixen el mateix restant (3) en dividir entre 10, o, equivalentement, 63 − 83 és un múltiple de 10. Es llig:

«63 és congruent en 83, mòdul 10», «en mòdul 10, 63 i 83 són congruents», o «63 i 83 són congruents un en un atre, mòdul 10».

«Mòdul» a voltes s'abrevia en la paraula «mod» en parlar, de la mateixa manera que com està escrit i prové de la paraula modulus del llatí, la llengua dels escrits originals de Gauss. Aixina, el número $n$, que en este eixemple és 10, seria el modulus.

Un atre eixemple; quan el mòdul és 12, llavors qualssevol dos números que dividits entre dotze donen el mateix restant són equivalents (o "congruents") un en un atre. Els números:

..., −34, −22, −10, 2, 14, 26,...

són tots "congruents mòdul 12" uns en uns atres, ya que cada u deixa el mateix restant (2) quan els dividim entre 12. La colecció de tots eixos números és una classe de congruència.

Propietats principals

Classes d'equivalència mòdul n

La aritmètica modular es basa en una relació d'equivalència, i les classes d'equivalència d'un sancer $a$ es denota en $[a{]}_n$ (o simplement $[a]$ si sobreentendemos el mòdul.) Atres notacions són per eixemple $a+nZ$ o $amodn$. El conjunt de totes les classes d'equivalència es denota en $Z/nZ=\{[0{]}_n,[1{]}_n,[2{]}_n,\mathrm{...},[n-1{]}_n\}$.

Esta relació d'equivalència té importants propietats que se seguixen immediatament de la definició:

Si

$a_1\equiv b_1(modn)$

i

$a_2\equiv b_2(modn)$

llavors

$a_1+a_2\equiv b_1+b_2(modn)$

i

$a_1\cdot a_2\equiv b_1\cdot b_2(modn)$

Lo que mostra que la suma i la multiplicació són operacions ben definides sobre el conjunt de les classes d'equivalència. En atres paraules, la suma i la multiplicació estan definides sobre $Z/nZ$ per mig de les fòrmules següents:

$[a{]}_n+[b{]}_n=[a+b{]}_n$

$[a{]}_n\cdot [b{]}_n=[a\cdot b{]}_n$

D'esta manera, $Z/nZ$ es convertix en un anell en $n$ elements. Per eixemple, en l'anell $Z/12Z$, es té:

$[8{]}_{12}\cdot [3{]}_{12}+[6{]}_{12}=[30{]}_{12}=[6{]}_{12}$

El conjunt de sancers en $Z/pZ$ forma un cos finito si, i només si, $p$ és primer.

Resolució de congruència

Si $a$ i $b$ són sancers, la congruència: $ax\equiv b(modn)$ té solució $x$ si, i només si, el màxim comú divisor de $(a,n)$ dividix a $b$. Els detalls estan arreplegats en el teorema de congruència llineal. Sistemes de congruència més complicats en mòduls diferents es poden resoldre usant el teorema chinenca del restant o el método de substitució successiva.

En l'anelle de sancers, si considerem l'equació $ax\equiv 1(modn)$, veem que $a$ té un invers multiplicativo si, i només si, $a$ i $n$ són coprimos (primers relatius). Per tant, $Z/nZ$ és un cos si, i només si, $n$ és un primer. Es pot provar que cada cos finito és una extensió de $Z/pZ$ per a algun primer $p$.

Menuda teorema de Fermat i teorema de Euler

Artícul principal → Menuda teorema de Fermat.

Un fet important sobre aritmètica modular, quan els mòduls són número primo és el menuda teorema de Fermat: si $p$ és un número primo, llavors:

Si $a$ és un número natural:

$a^p\equiv a(modp)$

Si $a$ és un número natural no divisible per $p$:

$a^{p-1}\equiv 1(modp)$

Açò va ser generalisat per Euler:

$\mathrm{\forall }n\in {\mathbb{Z}}^{+}{}_{\wedge }a\in \mathbb{Z}:\gcd (a,n)=1$ (Para tot sancer positiu $n$ i tot sancer $a$ relativament primer a $n$):

$a^{\varphi (n)}\equiv 1(modn)$

a on $\varphi (n)$ denota funció phi de Euler que conta el número de sancers entre 1 i $n$ que siguen coprimos sobre $n$. El teorema de Euler és una conseqüència del teorema de Lagrange, aplicat al cas del grup de les unitats de l'anell $Z/nZ$.

Generalisacions

Dos sancers $a$, $b$ són congruents mòdul $n$, escrit com: $a\equiv b(modn)$ si la seua diferència $a-b$ és divisible entre $n$, açò és, si $a-b=k\cdot n$ per a algun sancer $k$.

Usant esta definició, podem generalisar a mòduls no sancers. Per eixemple, podem definir $a\equiv b(mod2\cdot \pi )$, si $a-b=k\cdot 2\cdot \pi$, per a algun sancer $k$. Esta idea es desenrolla plenament en el context de la teoria dels anells i funcions trigonométricas.

En Àlgebra abstracta es veu que l'aritmètica modular és un cas especial del procés de crear un anelle cocient d'un anell mòdul un ideal. Si $R$ és un anell conmutativo, i $I$ és un ideal de $R$, llavors dos elements $a$ i $b$ de $R$ es diuen congruents mòdul $I$ si $a-b$ és un element de $I$. Com passava en l'anell de sancers, açò es convertix en una relació d'equivalència, i la suma i la multiplicació es convertixen en operacions ben definides sobre l'anell factorial $R/I$.

Proposicions bàsiques

Proposició 1

Siguen $a,b,c\in \mathbb{Z}$. Llavors es complixen les següents propietats:

1. <o>Reflexividad</o>: $a\equiv a(modn)$
2. <o>Simetria</o>: Si  $a\equiv b(modn)$, llavors $b\equiv a(modn)$.
3. <o>Transitividad</o>: Si  $a\equiv b(modn)$ i $b\equiv c(modn)$, llavors $a\equiv c(modn)$.

És dir, la congruència ($\equiv$) és una relació d'equivalència.

Proposició 2.

Sean a,b,c,d,λ∈ℤ i n∈ℕ tals que a≡b (mod n) i c≡d (mod n). Llavors

1. λa≡λb (mod n).
2. a+c≡b+d (mod n).
3. ac≡bd (mod n).

Proposició 3.

Sean a,b∈ℤ i n,k∈ℕ, tals que a≡b (mod n). Llavors ak≡bk (mod n).

Proposició 4.

Sean a,b∈ℤ i m,n∈ℕ. Si a≡b (mod n) i m|n llavors a≡b (mod m).

Proposició 5.

Sean a,b,c∈ℤ i n∈ℕ. Si ac≡bc (mod n) i (c,n)=1, llavors a≡b (mod n).

Proposició 6.

Sean a,b,c∈ℤ i p∈ℕ. Si ac≡bc (mod p) i p és primer tal que p∤c, llavors a≡b (mod p).

Proposició 7.

Sean a,b,c∈ℤ, n∈ℕ i (c,n)=d. Llavors ac≡bc (mod n) si i només si a≡b (mod n/d).

Divisió

Se sap que si $a\times b=1$, llavors $b$ és el recíproc o invers de $a$ i també $a$ és l'invers de $b$.

• Per eixemple, invers de a = 4 és b = 0.25 perque 4 · 0.25 = 1. L'invers del sancer 4 és el decimal (racional) 0.25.

• Esta és una anomalia que no volem en ℤ_n. Quisíeramos que en ℤ_n els inversos dels elements de ℤ_n estiguen en ℤ_n, com succeïx en els negatius. Pero açò no sempre succeïx. Per eixemple en ℤ₉ = {0, ..., 8}, cap element és invers de 3, perque cap número multiplicat per 3 donaria 1. Tindria que donar 10, per a que en prendre-ho mòdul 9, done 1, i eixe sancer no existix. No obstant 2 · 5 = 1. lo que revela que el 5 és l'invers del 2 i, simétricament, el 2 és l'invers de 5. Podem afirmar que en ℤ₉, el 2 és invertible, és dir té invers i el seu invers és 2⁻¹ = 5. Observa la notació: l'invers d'és a⁻¹. Contar en inversos és important perque nos permeten fer divisions i resoldre equacions. En efecte, la divisió a / b l'entenem com a · b⁻¹, és dir multipliquem a per l'invers del divisor b.

Teorema (Criteris de divisibilidad)

Siga $n=(a_p\mathrm{...}{a}_0{)}_{10}\in \mathbb{N}$ en base 10. Llavors $n=a_{p}10^p+a_{p-1}10^{p-1}+a_{p-2}10^{p-2}+\cdots +a_{2}10^2+a_{1}10+a_0$ i per tant,

1. $n\equiv a_0(\mathrm{mod}2)$, després $n$ és divisible entre 2 si i solament si $a_0$ lo és.
2. $n\equiv \sum _{i=0}^p{a}_i(\mathrm{mod}3)$, després $n$ és divisible entre 3 si i solament si $\sum _{i=0}^p{a}_i$ lo és.
3. $n\equiv 10a_1+a_0\equiv 2a_1+a_0(\mathrm{mod}4)$, després $n$ és divisible entre 4 si i solament si $(a_1{a}_0{)}_{10}$ lo és.
4. $n\equiv a_0(\mathrm{mod}5)$, després $n$ és divisible entre 5 si i solament si $a_0$ lo és.
5. $n\equiv \sum _{i=0}^p{a}_i(\mathrm{mod}9)$, després $n$ és divisible entre 9 si i solament si $\sum _{i=0}^p{a}_i$ lo és.
6. $n\equiv \sum _{i=0}^p(-1{)}^i{a}_i(\mathrm{mod}11)$, després $n$ és divisible entre 11 si i solament si $\sum _{i=0}^p(-1{)}^i{a}_i$

Multiplicació

Les operacions de suma i producte en ℤ es poden traslladar a ℤm posat que són compatibles en l'estructura d'este últim conjunt.

Teorema

Siguen m ∈ ℕ i a, b, c, d ∈ ℤ tals que a ≡ b (mod m) i c ≡ d (mod m). Llavors

i) a + c ≡ b + d (mod m),

ii) ac ≡ bd (mod m).

Equacions llineals de congruència

Definició 1

Siguen a,b∈ℤ; no nuls i n∈ℕ. Es denomina equació llineal de congruència a l'expressió ax≡b (mod n). L'número entero x: correspon a la solució de l'equació.

Les solucions d'una Equació Llineal de Congruència deuen ser número entero. ¿Existix algun criteri per a determinar quan una Equació Llineal de Congruència té solucions sanceres? La resposta és afirmativa.

Definició 2

Siguen a,b∈ℤ no nuls i n∈ℕ. L'equació ax≡b (mod n), té solució si i només si (a,n)|b.

No obstant (i novament, de la mateixa manera que en les equacions diofánticas llineals), una equació llineal de congruència pot posseir més d'una solució. Per lo tant, considerem el següent resultat (Definició 3).

Definició 3

Siguen a,b∈ℤ no nuls, n∈ℕ, (a,n)=d i d|b. Llavors la congruència ax≡b (mod n) té d soluciones. Adicionalment x≡x0+ntd (mod n), és el conjunt solució de l'equació, en t={1,2,3,...,d−1} i x0 és una solució particular de ax≡b (mod n). Els següents resultats permetran resoldre de manera més expedita una Equació Llineal de Congruència (Definició 4 i 5).

Definició 4

Siguen a,b∈ℤ i n,d∈ℕ. Si ad≡bd (mod nd), llavors a≡b (mod n).

Definició 5

Siguen a,b∈ℤ i n,d∈ℕ tals que (n,d)=1. Si ad≡bd (mod n), llavors a≡b (mod n).

¿És possible relacionar la funció φ de Euler en les equacions llineals de congruència? La Definició 6 té la resposta.

Definició 6

Siguen a,b∈ℤ no nuls, n∈ℕ i (a,n)=1. Llavors l'única solució a l'equació ax≡b (mod n) és x≡aφ(n)−1⋅b (mod n).

Aritmètica en números grans

Casi tots els processadors treballen molt més ràpit en números menuts que en números grans. Este problema pot resoldre's utilisant congruència. Per a això considerem un conjunt {m₁, m₂, . . . , m_k } de número primo entre sí (açò és mcd(m_i, m_j) = 1 per a tot i != j). Llavors qualsevol número positiu S menor que m = m₁m₂ · · · m_k es pot expressar per mig d'una n-tupla (r₁,r₂, . . . ,r_k ) (en 0 ≤ r_i < m_i per a tot i ∈ {1, 2, . . . , k}) a on

$\{\begin{array}{c}x\equiv r_{1}mod(m_1)\\ .\\ .\\ .\\ x\equiv r_{k}mod(m_k)\end{array}$

Ademés, pel teorema chinenca del restant existix un únic x ∈ {0, 1, 2, . . . , m} satisfent estes condicions. Ademés, si

$\{\begin{array}{c}x\equiv r_{1}mod(m_1)\\ .\\ .\\ .\\ x\equiv r_{k}mod(m_k)\end{array}y\{\begin{array}{c}{x}^{\prime }\equiv r{\text{'}}_{1}mod(m_1)\\ .\\ .\\ .\\ x^{\prime }\equiv r{\text{'}}_{k}mod(m_k)\end{array}$

Per tant, les operacions aritmètiques es poden realisar entre les r-uplas – les coordenades de la qual són totes menors o iguals que max1≤i≤r la meua –, podent-se realisar estes operacions en paralel. Açò és, per a sumar n i n' se sumen els vectores associats (r₁,r₂, . . . ,r_k ) i(r'₁,r'₂, . . . ,r'_k ) i per a multiplicar n i n' es multipliquen escalarment els vectores associats.

Finalment x + x' i xx' seran les solucions (úniques en ℤ_m) dels sistemes anteriors.

Per eixemple es poden considerar m₁ = 99, m₂ = 98, m₃ = 97 i m₄ = 95 per a treballar en números menors o iguals que m = m₁m₂m₃m₄ = 89403930.

Atres sancers que poden triar-se són els de la forma 2^k − 1 en k ∈ ℕ posat que és relativament fàcil trobar conjunts d'estos sancers cosins entre sí

(mcd(2^a − 1, 2^b −1) = 2^mcd(a,b) − 1). Ademés en estos sancers és fàcil treballar en base 2. Per eixemple, 2³⁵ − 1, 2³⁴ − 1, 2³³ − 1,2³¹ −1, 2²⁹ −1 i 2²³ −1 són primers entre sí i el producte d'ells és major que 2¹⁸⁴.

Eixemple: Si prenem m₁ = 3, m₂ = 4 es té que 0 = (0, 0), 1 = (1, 1), 2 = (2, 2), 3 = (0, 3), 4 = (1, 0), 5 = (2, 1), 6 = (0, 2), 7 = (1, 3), 8 = (2, 0), 9 = (0, 1), 10 = (1, 2) i 11 = (2, 3). Sengles eixemples de suma i producte són: 5 + 6 ≡ (2, 1) + (0, 2) = (2, 3) ≡ 11 i 2 · 3 ≡ (2, 2) · (0, 3) = (0, 6) ≡ (0, 2) ≡ 6. No obstant 5 · 6 no es pot calcular per mig d'este procediment, ya que el resultat 5 · 6 és major o igual que 12.

Aplicacions de l'aritmètica modular

L'aritmètica modular, estudiada sistemàticament en primer lloc per Carl Friedrich Gauss al final de el XVIII, s'aplica en teoria de números, àlgebra abstracta, criptografia, i en arts visuals i musicals.

En informàtica

Les operacions aritmètiques que hui en dia fan la majoria de les computadores són aritmètic modular, a on el mòdul és 2^b (b és el número de bits dels valors sobre els que operem). Açò es veu clar en la compilació de llenguages de programació com el C; a on per eixemple totes les operacions aritmètiques sobre "int", sancers, es prenen mòdul 2³² en la majoria de les computadores.

En criptografia

L'aritmètica modular és una ferramenta poderosa en criptografia. Permet la creació de sistemes de sifrat robusts com RSA, protegint l'informació i facilitant les comunicacions segures en el món digital.

En l'art

En música, per l'equivalència d'octaves i equivalència enarmònica (açò és, els passos en raons d'1/2 o 2/1 són equivalents, i Do# és lo mateix que Reb), l'aritmètica modular s'usa quan considerem l'escala de dotze tons igualment temperada, especialment en el dodecafonismo. En arts visuals esta aritmètica pot usar-se per a crear patrons artístics basats en les taules de multiplicació mòdul n (vore enllaç avall).

Vore també

• Residu quadràtic
• Teorema chinenca del restant
• Teoria de números
• Número primo
• Classe d'equivalència potencial
• Menuda teorema de Fermat
• Teorema de Euler
• Criteri de Euler
• Teorema de Lagrange (teoria de grups)
• Aritmètica de saturació
• Operació mòdul
• Restant
• Teorema de congruència llineal
• Principi d'inducció
• Reflexividad
• Simetria
• Transitividad
• Equació diofántica

Enllaços externs

• Modular arithmetic en MathWorld.
• Perl arithmetic enhancements - explica les raons que es troben despuix de l'operador de Perl %

Bibliografia

• http://www.matematicas.ciencias.uchile.cl/juaco/section-10.html
• http://serbal.pntic.mec.es/jpem0100/cesar/01.html

• https://www.cartagena99.com/recursos/alumnos/apuntes/tema3%20Aritmetica%20Modular.pdf