Forma rápida de encontrar el resto

Question

Tengo la siguiente pregunta:

Encuentra el resto de $29\times 2901\times 2017$ dividido por $17$

Ya tengo la respuesta (7) para este problema. Lo he resuelto por el camino largo, multiplicando todos los números y dividiéndolos por 17. Estoy pensando si hay alguna forma rápida de resolverlo. Mi solución lleva mucho tiempo.

Answer 1

Una pista:

Si $$a\equiv b\pmod c$$ Y $$d\equiv e\pmod c$$ Puedes multiplicar los dos para obtener $$a\times d\equiv b\times e\pmod c$$

Si haces esto para los números por separado y luego multiplicas las expresiones, obtendrás la solución muy rápidamente.

Answer 2

Puedes escribir cada número como un múltiplo de $17$ más un pequeño remanente:

$$(17+12)(170\cdot 17+11)(118\cdot 17+11).$$

Cuando se multiplica esto (lo cual no es necesario hacer) cada término es un múltiplo de $17$ excepto el último $12\cdot 11\cdot 11$ . Por lo tanto, hay que considerar sólo este último producto. Podemos repetir lo que acabamos de hacer con un poco de factorización. Lo anterior $= 3\cdot 11 \cdot 4 \cdot 11 = 33\cdot 44 = (17+16)(2\cdot 17 + 10).$ Así que sólo hay que tener en cuenta $16\cdot 10$ .

Answer 3

Hallar el resto después de dividir $29 \times 2901 \times 2017$ por $17$ .

Trabajo $\mod 17$ ¡!

\begin{align} & 29 \times 2901 \times 2017 \\ & 12 \times 1201 \times 317 \\ & 12 \times 1201 \times 147 \\ & 12 \times 351 \times 62 \\ & 12 \times 11 \times 11 \\ & 1452 \\ & 602 \\ & 92 \\ & 7. \end{align}

Answer 4

Esto puede hacerse en $15$ segundos de puramente mental aritmética modular de pequeño números utilizando el prueba de divisibilidad universal que es esencialmente el algoritmo de la división ignorando los cocientes. Para obtener una aceleración óptima utilizamos menor magnitud restos, por ejemplo $-1$ contra. $16\pmod{\!17}$ ya que al hacerlo se simplifica la aritmética posterior. Para reducir un número decimal mod $n$ modulamos continuamente los trozos iniciales de sus dígitos. Dado que permitimos residuos negativos, nos encontraremos con dígitos negativos, delimitados por una coma, por ejemplo $\,a,b := a(10)\!+\!b.\,$ Demostramos $\ 3247\equiv 0\pmod{\!17}\,$ para la práctica.

$\begin{align}{\rm mod}\ 17\!:\qquad &\,\ \color{#90f}{32}\ 47\\ \equiv\ &{\color{#90f}{-2}},\color{#0a0}47 \ \ \ \text{by }\ \ \ \ \ \,\color{#90f}{32}\,\equiv\,\color{#90f}{-2} \\ \equiv\ &\quad\ \ \, \color{#f84}{\bf 1}7\ \ \ \text{by }\ {\color{#90f}{-2}},\color{#0a0}4 \equiv\, \color{#90f}{{-}2}(10)\!+\!\color{#0a0}4\equiv -16\equiv \color{#f84}{\bf 1} \\[-.3em] \text{Let's do the number in the OP}\qquad\ \ \ \ \\[-.3em] &\,\ \color{#90f}{29}\ 01\\ \equiv\ & {\color{#90f}{-5}},\color{#0a0}01\ \ \text{ by }\quad \color{#90f}{29\,\equiv\, -5} \\ \equiv\ &\quad\ \ \color{#f84}{\bf 1}1\ \ \, \text{ by }\ \color{#90f}{{-}5},\color{#0a0}0\equiv {\color{#90f}{-5}(10)\!+\!\color{#0a0}0}\equiv -50\equiv\color{#f84}{\bf 1}\\ \equiv\ &\quad \,\color{#08f}{-6}\\[-.2em] \text{Similarly $\,2017\equiv\color{#c00}{-6}\ $ so we have}\phantom{MM}\\[-.2em] &\ 29\cdot 2901\cdot 2017\\ \equiv\ &(-5)(\color{#08f}{-6})(\color{#c00}{-6})\\ \equiv\ &(-5)\ \color{#08f} 2\\ \equiv\ &\ 7 \end{align}\qquad\qquad$

donde hemos aplicado el Reglas del producto de congruencia y de la suma muchas veces por encima.

Nota: $ $ Escribí cada pequeño detalle arriba para ayudar a evitar la confusión con los dígitos negativos. Una vez que se adquiere la destreza, no es necesario ser tan extremadamente verboso. Véase aquí para un ejemplo mayor que también emplea dígitos negativos para la optimización.

Answer 5

29 × 2901 × 2017 $\equiv$ 12 × 11 × 11 (mod 17)

12 × 121 $\equiv$ (mod. 17)

12 × 2 $\equiv$ (mod. 17)

24 $\equiv$ 7 (mod 17)