Cómo encontrar si un número entero ‘M’ es divisible por ‘N’ (número entero) o no sin usar la operación de división / módulo y tampoco se permiten bucles

Answer 1

Generalmente sí, pero puede ser complicado. Hagamos una división por 7 criterios.

[matemáticas] 1 = 1 (\ mod 7) [/ matemáticas]

[matemáticas] 10 = 3 (\ mod 7) [/ matemáticas]

[matemáticas] 10 ^ 2 = 2 (\ mod 7) [/ matemáticas]

[matemáticas] 10 ^ 3 = -1 (\ mod 7) [/ matemáticas]

[matemáticas] 10 ^ 4 = -3 (\ mod 7) [/ matemáticas]

[matemáticas] 10 ^ 5 = -2 (\ mod 7) [/ matemáticas]

[matemáticas] 10 ^ 6 = 1 (\ mod 7) [/ matemáticas] … y el patrón se repite.

Entonces, ¿cuál es el camino? Vamos a ver que el resto 12345678 de la división por 7

[matemáticas] 8 \ cdot 1 + 7 \ cdot 3 +6 \ cdot 2 +5 \ cdot (-1) +4 \ cdot (-3) +3 \ cdot (-2) +2 \ cdot 1 + 1 \ cdot 3 (\ mod 7) = 1 + 0 – 2 + 2 + 2 + 1 +2 +3 = 9 (\ mod 7) = 2 (\ mod 7) [/ matemática]

Por lo tanto, el resto es 2 y el número no se puede dividir por 7.

Si conoce la aritmética del módulo, puede hacer una tonelada de tales trucos.

Un ejemplo más: división por 7 en un sistema octal.

[matemáticas] 1 = 1 (\ mod 7), 8 = 1 (\ mod 7),… 8 ^ n = 1 (\ mod 7) [/ matemáticas]

Por lo tanto, solo sume todos los dígitos en un número octal y divídalos entre 7. Es decir [matemática] 123456_8 (\ mod 7) = (1 + 2 + 3 + 4 + 5 + 6) (\ mod 7) = (1 + 2 + 3–3–2–1) (\ mod 7) = 0 (\ mod 7) [/ math]. Es decir, [matemáticas] 123456_8 = 42798_ {10} [/ matemáticas] es divisible por 7.

Answer 2

Si N es una potencia de 2, se puede hacer fácilmente como sabes.

Si N es 1 menor que una potencia de 2, o [matemática] N = 2 ^ n – 1 [/ matemática] puede agregar los dígitos en la base [matemática] 2 ^ n [/ matemática], similar a sumar los dígitos en decimal para obtener el módulo 9 como lo usamos comúnmente.
¿Hay alguna forma de escribir “mod 31” sin operadores de módulo / división?

Si N es un valor pequeño, puede usar la forma descrita aquí Página en stackoverflow.com

Si N es una constante, puedes dividirla multiplicando por su inverso multiplicativo modular. Puedes encontrar la manera de hacerlo aquí Labor of Division (Episodio I).
Otro documento sobre esta página en gmplib.org
Más información: ¿Cuál es la forma más rápida de dividir un número entero entre 3 ?, dividir un número entre 5 sin usar el operador de división, dividir un número entre 3 sin usar los operadores *, /, +, -,%

Si N es solo un número arbitrario, no tiene otra forma que escribir una función de división. Una división simple se puede hacer como en matemáticas elementales. Si no puede usar bucles, debe desenrollarlo. Ya hay muchas soluciones que se pueden encontrar con una búsqueda en Google
división sin usar ‘/’
Implementar la división con un operador inteligente
¿Cómo puedo multiplicar y dividir usando solo desplazamiento y suma de bits?
Escribir una función de módulo usando solo suma / resta
¿Cómo puedo usar el desplazamiento de bits para reemplazar la división de enteros?
Cómo encontrar el resto sin división u operador de módulo en el ensamblaje MIPS

Answer 3

Para una potencia de 2, puede examinar los bits de orden inferior de un número binario, y si todos son cero, es divisible por esa potencia de 2.

Para los números en general, necesita división, o para imitar su implementación mediante la resta repetida del divisor, o potencias de 2 veces el divisor. No hay forma de evitar esto en general.