Reglas de divisibilidad y congruencias

Question

Lo siento si la pregunta es viejo, pero yo no era capaz de averiguar la respuesta todavía. Sé que hay un montón de reglas de divisibilidad, es decir: suma de dígitos, la alternativa de más y menos dígitos, etc... pero, ¿cómo puede alguien que se derivan de estas normas para cualquier número de $n$ digamos. Sé que se puede hacer uso de congruencias, pero ¿cómo ?

Gracias !

Answer 1

Uno no tiene que memorizar abigarrado exóticas pruebas de divisibilidad. No es un universal de la prueba de que es más sencillo y mucho más fácil de recordar, viz. evaluar un radix polinomio en anidados Horner forma, usando aritmética modular. Por ejemplo, considere la evaluación de un $3$ dígitos radix $10$ número modulo $7$. En Horner forma $\rm\ d_2\ d_1\ d_0 \ $ $\rm\: (d_2\cdot 10 + d_1)\ 10 + d_0\ \equiv\ (d_2\cdot 3 + d_1)\ 3 + d_0\ (mod\ 7)\ $ desde $\rm\ 10\equiv 3\ (mod\ 7)\:.\:$, por Lo que podemos calcular el resto $\rm\ (mod\ 7)\ $ como sigue. Comience con el primer dígito, a continuación, en repetidas ocasiones se aplican a la operación: multiplicar por $3$, a continuación, agregue el siguiente dígito, haciendo todas las de la aritmética $\rm\:(mod\ 7)\:.\:$

Por ejemplo, vamos a utilizar este algoritmo para reducir el $\rm\ 43211\ \:(mod\ 7)\:.\:$ El algoritmo consiste en varias ocasiones de la sustitución de los dos primeros dígitos iniciales $\rm\ d_n\ d_{n-1}\ $ $\rm\ d_n\cdot 3 + d_{n-1}\:\ (mod\ 7),\:$ es decir

$\rm\qquad\phantom{\equiv} \color{#C00}{4\ 3}\ 2\ 1\ 1$

$\rm\qquad\equiv\phantom{4} \color{green}{1\ 2}\ 1\ 1\quad $ $\rm\quad \color{#C00}4\cdot 3 + \color{#C00}3\ \equiv\ \color{green}1 $

$\rm\qquad\equiv\phantom{4\ 3} \color{royalblue}{5\ 1}\ 1\quad $ $\rm\quad \color{green}1\cdot 3 + \color{green}2\ \equiv\ \color{royalblue}5 $

$\rm\qquad\equiv\phantom{4\ 3\ 5} \color{brown}{2\ 1}\quad $ $\rm\quad \color{royalblue}5\cdot 3 + \color{royalblue}1\ \equiv\ \color{brown}2 $

$\rm\qquad\equiv\phantom{4\ 3\ 5\ 2} 0\quad $ $\rm\quad \color{brown}2\cdot 3 + \color{brown}1\ \equiv\ 0 $

Por lo tanto $\rm\ 43211\equiv 0\:\ (mod\ 7)\:,\:$ hecho $\rm\ 43211 = 7\cdot 6173\:.\:$ Generalmente la aritmética modular es más sencillo si se utiliza un sistema equilibrado de representantes, por ejemplo, $\rm\: \pm\{0,1,2,3\}\ \:(mod\ 7)\:.$ Aviso que para el módulo de $11$ o $9\:$ el método anterior se reduce a la conocida pruebas de divisibilidad por $11$ o $9\:$ (.k.a. "echa fuera a los nueves" para el módulo de $9\:$).

Answer 2

Un entero positivo escrito como $x = d_k \ldots d_1 d_0$ (en base 10) es realmente $\sum_{j=0}^k d_j 10^j$. Supongamos $10^j \equiv m_j \mod n$. A continuación, $x$ es divisible por $n$ si y sólo si $\sum_{j=0}^k d_j m_j$ es divisible por $n$. Asumiendo $n$ y 10 son coprime, $10^j$ es periódica mod $n$, el periodo mínimo de ser un divisor de a $\varphi(n)$.

Por ejemplo, en el caso de $n=7$, tenemos $m_0 = 1$, $m_1 = 3$, $m_2 = 2$, $m_3 = -1$, $m_4 = -3$, $m_5 = -2$, y luego se repite. Por lo $x$ es divisible por 7 si y sólo si $(d_0 - d_3 + d_6 - d_9 + \ldots) + 3 (d_1 - d_4 + d_7 - d_{10} + \ldots) + 2 (d_2 - d_5 + d_8 - d_{11} + \ldots)$ es.

Answer 3

He aquí un ejemplo... tal vez le ayudará a mostrar que algo es divisible por 3 si sus cifras son divisibles por 3. Escriba su número en notación expandida[el uso de Robert Israel notación]:

$N=\displaystyle\sum_{j=0}^n d_j10^j, d_j\in\{0,1,\dotsc,9\}$ (suponga $d_n\neq 0$)

Queremos saber si el número es divisible por 3; dijo lo que es equivalente, cuando este número es congruente a $0\pmod{3}$. Me dicen que es cuando la suma de los dígitos es divisible por 3. Para mostrar esto, tomamos nuestro número $N\pmod{3}$:

$\displaystyle\sum_{j=0}^n d_j10^j\equiv \displaystyle\sum_{j=0}^n d_j1^j =\displaystyle\sum_{j=0}^n d_j\pmod{3}\text{ and we see that}$

Al $\displaystyle\sum_{j=0}^n d_j\equiv0\pmod{3},~\displaystyle\sum_{j=0}^nd_j10^j$ es divisible por 3.