Un número cuando se divide por 2, 3, 4, 5, 6 hojas de un resto de 1, pero es dividido por 7 completamente.

Question

Me encontré con una pregunta que es la siguiente:

Encontrar el número más pequeño que deja resto 1 al dividirlo por 2, 3, 4, 5, 6 pero dividido por 7 completamente.

Lo que hice a continuación se da paso sabio.

Paso 1- Encontrar el MCM de 2, 3, 4, 5, 6, que es de 60.

Paso 2- Añadir de 1 a 60, que es de 61.

Paso 3- Múltiples 61 por 7 repetidamente hasta que se cumpla con la condición de que el resto debe ser de 1.

Paso 4- tengo la respuesta 146461 que parece correcto.

Así que ahora mi pregunta es:

1) ¿esta respuesta Es la correcta? Si es así ¿para verificar que este es el menor número que cumple la condición anterior?

2) creo que esta no es la mejor manera de hacer esta pregunta. Así que nadie Puede dar una mejor manera de resolver este problema?

Gracias de antemano

Answer 1

Usted necesita definitivamente $n\equiv 1\pmod {60}$$n\equiv 0\pmod 7$. Así que el truco es aplicar el teorema del resto Chino. Solucionar $60x+7y=1$$(x,y)=(2,-17)$.

A continuación, $n\equiv 1\cdot 7\cdot (-17)+0\cdot 60\cdot 2\pmod{420}$ o $n\equiv -119\pmod{420}$. El más pequeño tal número positivo es $420-119=301$.

Answer 2

Considere la posibilidad de $60k+1,$ $$60(7n)+1=420n+1$$ $$60(7n+1)+1=420n+61$$ $$60(7n+2)+1=420n+121$$ $$60(7n+3)+1=420n+181$$ $$60(7n+4)+1=420n+241$$ $$60(7n+5)+1=420n+301$$ $$60(7n+6)+1=420n+361.$$ Now by divisibility test for 7, among $1, 61, 121, 181, 241, 301, 361$, only $301$ is divisible by $7.$

Por lo tanto, cualquier número de la forma $420n+301$ satisface los requisitos dados.

Answer 3

He aquí otra manera de abordarlo. Ya imaginé que usted está buscando para $60k+1$. Cuando se multiplica $60$ $k$ desea un predecesor a una multiplicación de las $7$.

$60 \equiv 4 \pmod 7$ $5 \times 4 = 20$ que es un precursor de una multiplicación de las $7$.

Por lo $k=5$.

Answer 4

A continuación son algunos de los diferentes enfoques (además de la norma de Algoritmo de Euclides Extendido).

${\rm mod}\ 60\!:\ x\equiv 1\equiv 7n\!\iff\! n\equiv\dfrac{1}7\equiv \dfrac{-59}7\equiv \dfrac{-119}7\equiv -17\,$ $\,x = 7(\overbrace{-17\!+\!60k}^{\large n}) = 420k-119$

Alternativamente $\, $ mod $\,60\!:\ \color{#c00}{7^4\equiv 1}\,$ (por cierto mod $3,4,5)\,$ $\smash[b]{\,\color{#c00}{7^{-1}\equiv 7^3}\equiv 7(\underbrace{-11}_{\Large 7^2})\equiv -17}$

Alternativamente $ $ podemos emplear $ $ Inversa de la Reciprocidad

$\qquad \dfrac{1}7\ {\rm mod}\ 60\ \equiv\ \dfrac{1-60\overbrace{\left(\dfrac{1}{60}\ {\rm mod}\ 7\right)}^{\Large \color{#0a0}{\equiv\, 2}}}7\,\equiv\, \dfrac{-119}7 \,\equiv\, -17\ $

$\text{where we've used}\ \ {\rm mod}\ 7\!:\,\ \dfrac{1}{60}\equiv \dfrac{8}4\color{#0a0}{\equiv 2}$

Comentario $ $ En el primer método se encontró un numerador $\,-119\equiv 1\pmod{60}$ que también es divisible por $7$ por fuerza bruta, es decir, hemos probado $\,1-60k\,$$\,k=1,2\ldots$, Pero ahora vemos que la solución de $\,\color{#0a0}{ k\equiv 2}\,$ es simplemente el inverso del inverso $\, k \equiv 1/60\ \pmod 7.\,$

Answer 5

Ya que nadie lo ha mencionado en sus respuestas hasta ahora, su paso 3 está mal, o al menos desacertado, en la que usted viene a través de una gran cantidad de respuestas que no cumplan con sus cuidadosamente-set-up de la satisfacción de los primeros cinco condiciones. Por ejemplo, $61\times 7 = 427$ no cumple con la deseada restos de $4$ o $5$.

El problema es que han abandonado la seguridad de $n\equiv 1 \bmod 60$. La manera de retener a este en una búsqueda simple es agregar 60 repetidamente buscando la divisibilidad por 7.

Podemos hacer un poco mejor que eso, sin embargo. Podemos traducir en números más pequeños para hacer la vida más fácil para nosotros mismos. $60 \equiv 4 \bmod 7$ (y, por supuesto,$61 \equiv 5 \bmod 7$) entonces nos preguntamos: ¿cuántos 4s tenemos que añadir a 5 antes de que la respuesta es divisible por 7?

De nuevo podemos slog a través de las posibilidades, pero los múltiplos de 7 son más fáciles de sobrellevar. Añadimos dos 4s (13 - y tal vez ver que hemos llegado a $6 \bmod 7$) y añadir otros dos 4s para llegar a $21 \equiv 7 \equiv 0 \bmod 7$ - la adición de cuatro 4s por completo. Así que de vuelta en nuestro Problema Real, tenemos que añadir cuatro de los 60 - $4\times 60=240$ a nuestros original $61$ $ 240+61=301$ para los más pequeños solución positiva.

Tenga en cuenta que $60$ es su intervalo entre la satisfacción de los 5 primeros condiciones, sino que también han comenzado nuestra búsqueda a $1$ rathe de $61$, con (por supuesto) el mismo resultado final.