Leyes aritméticas de congruencia, por ejemplo, en la prueba de divisibilidad por 7

Question

Leyes aritméticas de congruencia, por ejemplo, en la prueba de divisibilidad por 7

Matemáticas
divisibilidad
teoría-de-números-elemental

Fuente matemática

He visto otros criterios para la divisibilidad por $7$ . El criterio descrito a continuación presente en el libro Handbook of Mathematics de IN Bronshtein (p. 323) es interesante, pero no pudo probarlo. Dejar $n = (a_ka_{k-1}\ldots a_2a_1a_0)_{10} = \displaystyle{\sum_{j=0}^{k}}a_{k-j}10^{k-j}$ . La expresion

q_{3}^{'} (norte) = (a_{2} a_{1} a_{0})_{10} - (a_{5} a_{4} a_{3})_{10} + (a_{8} a_{7} a_{6})_{10} - \dots

$Q_{3}^{\prime}(n) = (a_2a_1a_0)_{10} - (a_5a_4a_3)_{10} + (a_8a_7a_6)_{10} -\ldots$ se denominan sumas alternas de las cifras de tercer orden de

n

$n$ . Por ejemplo,

q_{3}^{'} (123456789) = 789 - 456 + 123 = 456

$Q_{3}^{\prime}(123456789) = 789-456+123=456$ Proposición:

7 | n \Leftrightarrow 7 | Q_{3}^{'} (n)

$7 | n \ \Leftrightarrow \ 7 | Q_{3}^{\prime}(n)$ .

¿Cuál sería la prueba de esto?

Gracias por cualquier ayuda.

Hubble

¿Has probado la inducción en

n

$n$ ?

Fuente matemática

El problema de la inducción es que hay varios casos a considerar.

laboratorio bhattacharjee

Consulte también: math.stackexchange.com/questions/328562/…

Respuestas (9)

Leyes aritméticas de congruencia, por ejemplo, en la prueba de divisibilidad por 7

El problema de la inducción es que hay varios casos a considerar.
Consulte también: math.stackexchange.com/questions/328562/…

Bill Dubuque · Answer 1

Nota $n = c_0\! + c_1 1000 + \cdots\! + c_k 1000^k\! = f(1000)$ es un polinomio en $1000$ con coeficientes enteros $\,c_i\,$ de este modo $\,{\rm mod}\ 7\!:\ \color{#c00}{1000}\equiv 10^3\equiv 3^3\equiv \color{#c00}{-1}\,\Rightarrow\, n = f(\color{#c00}{1000})\equiv f(\color{#c00}{-1}) \equiv c_0 - c_1 + \cdots + (-1)^k c_k$ sigue aplicando la regla de congruencia polinomial a continuación.

Similarmente $\!\bmod 7\!:\ \color{#c00}{100\equiv 2}\Rightarrow n = f(\color{#c00}{100})\equiv f(\color{#c00}2)\,$ dónde $f$ es su raíz $100$ polinomio como el anterior.

[ Nota Si las congruencias no le son familiares, entonces vea las reglas en forma de divisibilidad ]

A continuación se encuentran las reglas básicas de congruencia.Dejar $\rm\ A,B,a,b,m\,$ ser cualquier número entero.

Regla de la suma de congruencia $\rm\qquad\quad A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#90f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$

Prueba $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#90f}{A+B - (a+b)}$

Regla del producto de congruencia $\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{#0a0}{AB\equiv ab}\ \ \ (mod\ m)$

Prueba $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{#0a0}{AB - ab}$

Regla de potencia de congruencia $\rm\qquad \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \ (mod\ m)\ \$ para todos los naturales $\rm\,n.$

Prueba $\$ Para $\rm\,n=0\,$ es $\,1\equiv 1\,$ tan verdadero. $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,$ por la regla del producto, por lo que se sigue por inducción sobre $\rm\,n.\$ Advertencia , esto no sigue siendo cierto de manera más general si también reemplazamos de manera análoga el poder $\,\rm n\,$ por cualquiera $\rm\,N\equiv n\pmod{\! m},\,$ consulte "Cuidado" a continuación.

Regla inversa de congruencia $\rm \quad\ \color{#c00}{A\equiv a}\ \Rightarrow\ A^{-1}\equiv a^{-1},\$ si $\rm\,A^{-1}\,$ existe

Prueba $\rm\,\ A^{-1} \equiv A^{-1} \color{#c00}a a^{-1}\equiv A^{-1} \color{#c00}A a^{-1} \equiv a^{-1}$ por PR = Regla de Producto(nota $\rm\, a^{-1}$ existe por $\,\rm \color{#c00}aA^{-1}\equiv \color{#c00}AA^{-1}\equiv 1\,$ por PR). Alternativamente: si $\rm\, A^{-1}\equiv b\,$ entonces relaciones públicas $\rm\Rightarrow 1\equiv \color{#c00}Ab\equiv \color{#c00}ab\,$ entonces $\rm\, {a}^{-1} \equiv b\equiv A^{-1}\,$ por unicidad de inversas .

Regla del cociente de congruencia Si $\rm\,(B,n)= 1\,$ entonces $\rm\!\bmod n\!:\, {\begin{align}\rm A\equiv a\\ \rm B\equiv b\end{align}\,\Rightarrow\, \dfrac{A}B\equiv \dfrac{a}b\:\! \overset{\rm def}\equiv\, ab^{-1}}$
Prueba $\$ Ver esta respuesta , y ver aquí para fracciones modulares .

Regla de congruencia de polinomios $\$ Si $\rm\,f(x)\,$ es polinomial con coeficientes enteros entonces $\rm\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.\$ Nota: esto es equivalente al Teorema del Factor .

Prueba $\$ Por inducción en $\rm\, n =$ grado $\rm f.\,$ claro si $\rm\, n = 0.\,$ Demás $\rm\,f(x) = f(0) + x\,g(x)\,$ para $\rm\,g(x)\,$ un polinomio con coeficientes enteros de grado $\rm < n.\,$ por inducción $\rm g(A)\equiv g(a)$ entonces $\rm \color{#0a0}{A g(A)\equiv\! a g(a)}\,$ por la regla del producto. Por eso $\rm \,f(A) = f(0)+\color{#0a0}{Ag(A)}\equiv f(0)+\color{#0a0}{ag(a)} = f(a)\,$ por la regla de la suma.

Tener cuidado que tales reglas no necesitan ser ciertas para otras operaciones, por ejemplo, el análogo exponencial de arriba $\rm A^B\equiv\, a^b$ generalmente no es cierto (a menos que $\rm B = b,\,$ entonces se sigue por la regla de la potencia, o la regla del polinomio con $\rm\,f(x) = x^{\rm b}),$ p.ej $\rm\!\bmod {\rm prime}\ p\!:\ \color{#c00}{p\equiv 0}\,$ pero $\rm\,a^{\large\color{#c00} p}\equiv a^{ \color{#c00}0}\!\!\iff\! a\equiv 1,\,$ por el pequeño Fermat. Pero hay una regla más limitada para potencias enteras: consulte reducción de orden modular ,

Para la demostración de la regla de la potencia de congruencia, ¿por qué es $A^{n+1}$ ≡a $^{n+1}$ ?
@com Aplicamos la regla del producto a las dos congruencias anteriores en esa prueba.
¿Y es por conveniencia que omite el mod m en A≡a mod(m) y B≡b mod(m)?
@com No es necesario seguir repitiéndolo cuando solo hay un módulo involucrado (por lo que no hay ambigüedad).
En la prueba de la regla del producto de congruencia, ¿cómo hiciste esta inferencia - m| (A−a) B+a (B−b) de los dos primeros - m|(A - a) ym | (B - b)?
@com Si $\ J = jm,\,$ y $K = km\$ son múltiplos de $\,m\,$ entonces también lo es cualquier $\rm\color{#c00}{integral}$ combinación lineal $\, a\,J+b\,K =\, ajm + bkm\, =\, (aj + bk)m,\,$ para cualquier $\rm\color{#c00}{\,integers}\,$ $\,a,b.\$ O, dicho de manera equivalente, nótese que $\,m\,$ divide una suma si divide cada sumando (o algún factor de cada sumando), usando la ley distributiva para sacar un factor de $\,m\,$ fuera de la suma. $\ \$
Oh, aunque A se define como algo que cuando se resta por a es múltiplo de m, ¿todavía cuenta como un número entero?
Debido a que definiste tu caso base como n=1, ¿seguiría funcionando tu prueba de la regla de potencia de congruencia para n=0?
@com $\rm \ A,B,a,b\,$ son todos enteros por hipótesis (implícita). Podrías comenzar la inducción en $\,n=0\,$ si desea incluir ese caso en la Regla.
No entiendo tu demostración de la regla de congruencia de polinomios, ¿de dónde sacaste $p(n)$ a $p(n+1)$ ?
@YoTengoUnLCD Es una inducción fuerte con hipótesis inductiva: asumiendo que es cierta para todos los polinomios de grado $< n$ mostramos que es cierto para cualquier polinomio de grado $\,n.\ \$
@BillDubuque: Para la "Regla de la suma de congruencia", entiendo por qué $m \mid (A−a)+(B−b)$ y que reordenando los términos tenemos que $m \mid A+B−(a+b)$ . Pero no entendí cómo de eso deducimos que $A+B \equiv a+b$ . ¿Podrías ayudarme con esa parte?
@Jim Por hipótesis ambos sumando $\,A-a\,$ y $\,B-b\,$ son múltiplos de $m$ por lo tanto, también lo es su suma, ya que los múltiplos son cerrados bajo combinaciones lineales integrales .

cristian blatter · Answer 2

Desde $1001=143\cdot7$ resulta que $1000^k=(-1)^k$ módulo $7$ $(k\geq0)$ . De esto podemos deducir que

\sum_{k \geq 0}^{norte} a_{k} 1000^{k} = \sum_{k \geq 0} (- 1)^{k} a_{k} (metro o d tu yo o 7) .

$\sum_{k\geq0}^n a_k\>1000^k=\sum_{k\geq0}(-1)^k a_k\quad({\rm modulo}\ 7)\ .$

Entonces, realmente ha demostrado que "la suma alterna de los dígitos de tercer orden de $n$ " es equivalente $\mod 1001$ a $n$ . Y como 7 (y 13 y 11) son factores de 1001 la equivalencia también es $\mod 7$ (y $\mod 11$ y $\mod 13$ )

Cosrotash · Answer 3

13 \times 7 \times 11 = 1001 A = \bar{. . . a_{4} a_{3} a_{2} a_{1} a_{0}} A = a_{0} + 10 a_{1} + 100 a_{2} + 1000 a_{3} + 10000 a_{4} + 100000 a_{5} + 10^{6} a_{6} + . . . = (a_{0} + 10 a_{1} + 100 a_{2}) + (1000 a_{3} + 10000 a_{4} + 10^{5} a_{5}) + (10^{6} a_{6} + 10^{7} a_{7} + 10^{8} a_{8}) + . . . = (a_{0} + 10 a_{1} + 100 a_{2}) + 1000 (a_{3} + 10 a_{4} + 100 a_{5}) + 1000^{2} (a_{6} + 10 a_{7} + 100 a_{8}) + . . . (\bar{a_{2} a_{1} a_{0}}) + 1000 (\bar{a_{5} a_{4} a_{3}}) + 1000^{2} (\bar{a_{8} a_{7} a_{6}}) + . . . (\bar{a_{2} a_{1} a_{0}}) + (1001 - 1) (\bar{a_{5} a_{4} a_{3}}) + (1001 - 1)^{2} (\bar{a_{8} a_{7} a_{6}}) + . . . = (\bar{a_{2} a_{1} a_{0}}) + (7 k - 1) (\bar{a_{5} a_{4} a_{3}}) + (7 q - 1)^{2} (\bar{a_{8} a_{7} a_{6}}) + . . . = (\bar{a_{2} a_{1} a_{0}}) - 1 (\bar{a_{5} a_{4} a_{3}}) + 1 (\bar{a_{8} a_{7} a_{6}}) + . . . + \overset{7 q^{'}}{\overset{⏞}{7 k + 7 q + . . .}}

$\quad{13\times7\times 11=1001\\A= \overline{...a_4a_3a_2a_1a_0}\\A=a_0+10a_1+100a_2+1000a_3+10000a_4+100000a_5+10^6a_6+...=\\(a_0+10a_1+100a_2)+(1000a_3+10000a_4+10^5a_5)+(10^6a_6+10^7a_7+10^8a_8)+...\\=(a_0+10a_1+100a_2)+1000(a_3+10a_4+100a_5)+1000^2(a_6+10a_7+100a_8)+...\\(\overline{a_2a_1a_0})+1000(\overline{a_5a_4a_3})+1000^2(\overline{a_8a_7a_6})+...\\(\overline{a_2a_1a_0})+(1001-1)(\overline{a_5a_4a_3})+(1001-1)^2(\overline{a_8a_7a_6})+...=\\(\overline{a_2a_1a_0})+(7k-1)(\overline{a_5a_4a_3})+(7q-1)^2(\overline{a_8a_7a_6})+...=\\(\overline{a_2a_1a_0})-1(\overline{a_5a_4a_3})+1(\overline{a_8a_7a_6})+...+\overbrace{7k+7q+...}^{7q'}\\ }$ entonces si A dividido por 7

A = (\bar{a_{2} a_{1} a_{0}}) - 1 (\bar{a_{5} a_{4} a_{3}}) + 1 (\bar{a_{8} a_{7} a_{6}}) + . . . + \overset{7 q^{'}}{\overset{⏞}{7 k + 7 q + . . .}} A - 7 q = (\bar{a_{2} a_{1} a_{0}}) - 1 (\bar{a_{5} a_{4} a_{3}}) + 1 (\bar{a_{8} a_{7} a_{6}}) + . . .

$\quad{A = \space (\overline{a_2a_1a_0})-1(\overline{a_5a_4a_3})+1(\overline{a_8a_7a_6})+...+\overbrace{7k+7q+...}^{7q'}\\A-7Q=(\overline{a_2a_1a_0})-1(\overline{a_5a_4a_3})+1(\overline{a_8a_7a_6})+...}$

Hubble · Answer 4

Pista. $10^{6k}-1 \equiv 10^{6k - 3}+1 \equiv 0 \pmod{7}$ .

Adren · Answer 5

Esta no es una respuesta, sino otro criterio interesante para la divisibilidad por 7

Considerar $n\in\mathbb{N}$ y dividirlo por $10$ :

norte = 10 q + r w i t h 0 \leq r < 10

$n=10q+r\qquad\mathrm{with}\,0\le r<10$

Entonces nosotros tenemos :

7 ∣ norte \Leftrightarrow 7 ∣ q - 2 r

$7\mid n\Leftrightarrow 7\mid q-2r$

La demostración es muy fácil:

Suponer $7\mid n$ . Tenemos $n=7k$ para algún entero no negativo $k$ . Entonces $q-2r=q-2(n-10q)=21q-2n=7(3q-2k)$ .
Por el contrario, supongamos $7\mid q-2r$ . Tenemos $q-2r=7K$ para algún entero no negativo $K$ . Entonces $n=10(q-2r)+21r=7(10K+3r)$

Este criterio debe combinarse con la iteración para mostrar todo su poder... He aquí un ejemplo:

Para $n=22925$ , calculamos $q=2292$ , $r=5$ y $q-2r=2282$

Para $n=2282$ , calculamos $q=228$ , $r=2$ y $q-2r=224$

Para $n=224$ , calculamos $q=22$ , $r=4$ y $q-2r=14$

Desde $7\mid14$ y aplicando tres veces los criterios anteriores, concluimos que $7\mid22925$ .

El hecho pertinente aquí es que $7\mid 21$ . El método muestra correctamente si 7 divide o no un entero dado $n$ . Desafortunadamente, no determina $n\bmod 7$ excepto cuando es 0.

LAAE · Answer 6

Creo que este método puede reducirse usando tres coeficientes. $(1, 2, 3)$ saber si un número es múltiplo de siete o no. Multiplicamos el último número por $1$ , el segundo desde la derecha por $3$ , y finalmente por $2$ . Luego, los siguientes tres dígitos por $(-1, -3, -2)$ y otra vez por positivo. Por ejemplo:

$123456789$

$1 \cdot 9 + 3 \cdot 8 + 2 \cdot 7 -1 \cdot 6 -3 \cdot 5 -2 \cdot 4 + 1 \cdot 3 + 3 \cdot 2 + 2 \cdot 1 =$

$=47 - 29 + 11 = 29$

Número $29$ no es divisible por $7$ , así es el número $123456789$

Sin embargo, personalmente prefiero una fórmula simple:

$3 \times F + L$

$L$ - último dígito

$F$ - todo lo que está delante del último dígito.

entonces el numero $105$ Se puede escribir como: $3 \cdot 10 + 5=35$ que es divisible por $7$ , así es el número $105$ .

Espero que eso ayude un poco.

joffan · Answer 7

Para una idea simple:

Toma algún número $k<1000$ . ahora claramente $k$ tiene algo de sobra $r$ (que puede ser $0$ ) cuando se divide por $7$ . O, para decir lo mismo, $7$ divide $k-r$ .

que pasa cuando multiplicamos $k$ por $1000$ ?

Lo sabemos $7$ divide $1001$ y $7$ divide $k-r$ entonces $7$ divide $1001k - (k-r)$ $= 1000k - (-r)$ . Entonces podemos decir que $-r$ es el resto de $1000k$ dividido por $7$ . (Para obtener un resto positivo, simplemente tome $7-r$ ).

que pasa cuando multiplicamos $k$ por $1000000$ ?

Lo sabemos $7$ divide $1001$ y $7$ divide $1000k- (-r)$ entonces $7$ divide $1001\cdot 1000k - (1000k- (-r))$ $= 1000000k - r$ . Así que volvemos a $r$ como el resto.

Para probar esto correctamente se requiere aritmética modular, o un par de pasos de inducción, pero aun así el patrón es evidente; cada vez que multiplicamos por $1000$ , el resto de la división por $7$ signo inverso. Lo que significa que podemos ir un poco más allá de la afirmación original; no podemos simplemente encontrar la divisibilidad por $7$ mirando la suma alterna de tercer orden, pero también el resto si el número no es divisible por $7$ .

Yuri Negometianov · Answer 8

En notación octal, el criterio de divisibilidad por $7$ es similar al criterio de divisibilidad por $9$ en el decimal: si la suma de los dígitos octales del número se divide por $7$ , entonces el número en sí también lo es. Por ejemplo,

1001_{10} = 1751_{8} \to 1_{8} + 7_{8} + 5_{8} + 1_{8} = {dieciséis}_{8} \to 1_{8} + 6_{8} = 7_{8} ⋮ 7.

$1001_{10} = 1751_{8} \rightarrow 1_8 + 7_8 + 5_8 + 1_8 = 16_8 \rightarrow 1_8 + 6_8 = 7_8 \vdots 7.$

De esta forma, el criterio se puede utilizar para controlar el momento de transición de un formato de número fijo a flotante en lenguajes de programación con una tipificación de datos no estricta.

Pero si está preparado para encontrar la representación en base 8 de su número dado, ¿por qué no encontrar su representación en base 7? Y solo necesitas el último dígito de eso.
@RosieF Gracias por la sugerente pregunta, he complementado la respuesta.

shendi zhjeqi · Answer 9

Tenga en cuenta que $1001$ es divisible por $7$ , por eso, $1000 \equiv -1 (\bmod 7)$ .

Dejar, $n = a_0 + 10^1a_1+\ldots +10^ka_k$ .

Dividir $(a_0,\ldots,a_k)$ en grupos de tres para obtener

norte = \sum_{i = 0} 10^{3 i} (a_{i} + 10^{1} a_{i + 1} + 10^{2} a_{i + 2}) \equiv \sum_{i = 0} (- 1)^{i} (a_{i} + 10^{1} a_{i + 1} + 10^{2} a_{i + 2}) (modificación 7)

$n=\sum_{i=0}10^{3i}(a_i+10^1a_{i+1}+10^2a_{i+2})\equiv\sum_{i=0}(-1)^{i}(a_i+10^1a_{i + 1}+10^2a_{i + 2}) (\bmod 7)$

Y eso es exactamente lo que estábamos tratando de probar.

Leyes aritméticas de congruencia, por ejemplo, en la prueba de divisibilidad por 7

Fuente matemática

Hubble

Fuente matemática

laboratorio bhattacharjee

Respuestas (9)

Bill Dubuque

comprometidoandroid

Bill Dubuque

comprometidoandroid

Bill Dubuque

comprometidoandroid

Bill Dubuque

comprometidoandroid

comprometidoandroid

Bill Dubuque

YoTengoUnLCD

Bill Dubuque

Jim

Bill Dubuque

cristian blatter

Χpẘ

Cosrotash

Hubble

Adren

rosa f

LAAE

joffan

Yuri Negometianov

rosa f

Yuri Negometianov

shendi zhjeqi