La secuencia de números enteros $1, 11, 111, 1111, \ldots $ tienen dos elementos cuya diferencia es divisible por $2017$

Question

Demuestra que la secuencia $\{1, 11, 111, 1111, . \ldots\ }$ contendrá dos números cuya diferencia es un múltiplo de $2017$ .

He estado computando algunos de los múltiplos inmediatos de $2017$ para ver cómo son sus clases de congruencia, pero no estoy seguro de a dónde me lleva eso. Todo lo que sé ahora mismo es que la diferencia tendrá la forma $11 \ldots1100\ldots 00$ y esa es la diferencia: $(a-b) \mod 2017=0$ donde $a,b$ pertenecen a la secuencia.

Answer 1

La clave aquí es que hay números infinitos. Usando el principio del casillero se puede ver que debería haber dos números cuando se dividen por 2017 dan el mismo residuo y concluyen.

Answer 2

Aunque la forma correcta de hacer este problema es utilizar el principio de encasillamiento, uno puede tener curiosidad por encontrar un número específico que funcione:
Es decir, escribir un algoritmo que lo encuentre, dado que los números involucrados pueden ser grandes.
Resulta que esto no es demasiado difícil, aquí está el resultado:

Si $a= \\ 550873133917258855285627719936098716465597972786867184487412548889990635156723 \\ 406599460144328761086321820084834462623257863713986668870159202335702087809177 \\ 546411061532529058557814135404616316862226629207293560293064507243981711011953 \\ 947006004517159698121522613342147303476009475017903376852310912796782900897923 \\ 208285131934115573183495840907838924695642593510714482454690684735305459152757 \\ 120035255880570704566738280174075910317853798270258359499807194403128959400650 \\ 030298022365449237040709524596485429405607888503277695146807690188949484933619 \\ 787362970307938081859747700104665895444279182504269266787858756128463614829504 \\ 765052608384289098220679777447253897427422464606401145816118547898418994105657 \\ 467085330248443783396683743733818101691180521125984685726877100203823059549385 \\ 776455682256376356525092271249931140858260342643089296535007987660441800253401 \\ 641601939073431388751170605409574175067481958904864209772489395692172092767035 \\ 751666391230099708037239023852806698617308433867680273233074422960392221671349 \\ 088304963366936594502286123505756624249435355037734809673332231587065498815622 \\ 762077893461135900402137387759598964358508235553352063019886520134413044675811 \\ 160689693163664408086817605905359995593014928661929157714978240511210268275216 \\ 217705062524100699608880074918746212747204318845369911309425439321324299013937 \\ 090288106649038726381314383297526579628711507739767531537486916763069465102186 \\ 966341651517655483942048146311904368423951963862722415027819093262821572191924 \\ 199856772985181512697625736792816614333718944527075414532033272737288602434859 \\ 251914284140362474522117556326777943039717952955434363466093758607392717457169 \\ 613837933124001542444774968324794799757615821076406103674323803228116564755136 \\ 891973778438825538478488404120531041701096237536495345122018399162672836445766 \\ 539965845865697129950972291081363961879579132925687214234561780421968820580620 \\ 283148790833471051616812648047154740263317358012449732826530050129455186470555 \\ 83099212251418498319836941552360491378835454194898914779926183 $

entonces $b=a \cdot2017 =111 \cdots11 $ un total de $2016$ dígitos $1$ (y ningún otro dígito).

Por lo tanto $(10 \cdot a) \cdot2017 =10 \cdot b=111 \cdots110 $ un total de $2016$ dígitos $1$ seguido de un $0$ ,
que es $(10 \cdot a) \cdot2017 =111 \cdots111 -1$ donde el $111 \cdots111 $ tiene $2017$ dígitos $1$ 's.

A continuación, la descripción informal del algoritmo.
Empezando por $2017$ necesitamos multiplicarnos por $3$ para hacer que el último dígito $1$ :
$2017 \cdot3 =6051$ .
Entonces queremos mantener el último $1$ y convertir el penúltimo $5$ en $1$ .
Sabemos que $5+6=11$ y $7 \cdot8 =56$ por lo tanto nos multiplicamos $2017 \cdot80 =161360$ y añadir esto a $6051$ para obtener $167411$ .
Ahora tenemos que fijar el penúltimo dígito que es $4$ . Desde $4+7=11$ esta vez necesitamos multiplicar $2017 \cdot1\cdot10 ^2=201700$ y añadir esto a $167411$ para obtener $2017 \cdot183 =369111$ que son tres dígitos correctos $1$ está al final. Sabemos que si hacemos esto durante el tiempo suficiente, entonces (por el principio de encasillamiento) necesitamos obtener un número que consista en dígitos $1$ sólo (llamado repunit), y esto toma un segundo o dos en una computadora. Utilicé la función $f(c)$ donde $c$ es el "dígito a corregir", es decir, multiplicamos $2017$ por $f(c) \cdot10 ^k$ (donde $k$ aumenta gradualmente), donde $f(0)=3$ , $f(1)=0$ , $f(2)=7$ , $f(3)=4$ , $f(4)=1$ , $f(5)=8$ , $f(6)=5$ , $f(7)=2$ , $f(8)=9$ , $f(9)=6$ . Este $f$ tiene la propiedad de que $c+f(c) \cdot7 $ termina en $1$ para $c=0,1, \cdots ,9$ .

Editar. Después de hacer lo anterior a lo largo, me doy cuenta de que el comentario de @Phicar (después de la OP) muestra una forma más corta de hacerlo, usando el Pequeño Teorema de Fermat. En particular el número $a=5508 \cdots183 $ que se me ocurrió arriba es exactamente $a= \displaystyle ( \frac {10^{2017-1}-1}{10-1})/2017=( \frac {10^{2016}-1}9)/2017$ . Uno puede encontrar mucho más en línea, google repunit factorization, da resultados en Wikipedia, MathWorld, algunos artículos en pdf de Snyder 1982, Jaroma 2007, y una discusión en https://mathlesstraveled.com/2011/11/17/fun-with-repunit-divisors-more-solutions/ (por el Dr. Brent Yorgey).

Tengo que pensar en cómo el algoritmo descrito anteriormente se relaciona con el Pequeño Teorema de Fermat. Creo que el algoritmo funcionaría para cualquier número $k$ (no necesariamente un primo) que no es un múltiplo de $2$ o $5$ para producir un reembolso divisible por $k$ Me pregunto cuántos "pasos" podría dar, en términos de los factores de $k$ .

Editar. Hay al menos otras seis preguntas de MSE (algunas bastante viejas) discutiendo este tema. En general, las respuestas son de dos tipos: Ya sea usando el principio del casillero, o, alternativamente, tratando de ser más específicos y llegar a una respuesta particular que es un múltiplo del número en cuestión. Esto último puede implicar el Pequeño Teorema de Fermat, o algún enfoque algorítmico. A continuación figuran enlaces a algunas de estas preguntas, a título de referencia (las preguntas más antiguas primero, y sin hacer hincapié en ninguna respuesta en particular). (Seguramente he pasado por alto algunas, por favor siéntase libre de añadir más enlaces en un comentario).

Priyank Bhatnagar ( http://math.stackexchange.com/users/19802/priyank-bhatnagar ), Un número natural multiplicado por algún número entero da como resultado un número con sólo unos y ceros, URL (versión: 2015-04-25): Un número natural multiplicado por algún número entero resulta en un número con sólo unos y ceros

Ocho ( http://math.stackexchange.com/users/20036/eight ), probar que cada número que termina en un $3$ tiene un múltiplo que consiste sólo en unos, URL (versión: 2012-07-01): Demuestra que cada número que termina en un $3$ tiene un múltiplo que consiste sólo en unos.

HowardRoark ( http://math.stackexchange.com/users/32668/howardroark ), Todos los primos impar excepto $5$ dividir un número compuesto por todos $1$ s, URL (versión: 2012-07-01): Todos los primos del impar excepto $5$ dividir un número compuesto por todos $1$ s

usuario1526710 ( http://math.stackexchange.com/users/43178/user1526710 ), Principio de Divisibilidad y Agujero de Paloma, URL (versión: 2012-09-30): Principio de Divisibilidad y Pigeonhole

limp_chimp ( http://math.stackexchange.com/users/44186/limp-chimp ), pruebe que cada número entero $n>0$ con $ \gcd (n,10) = 1$ tiene un múltiplo que puede ser escrito con sólo el dígito $9$ ., URL (versión: 2012-11-04): Demuestra que cada número entero $n>0$ con $ \gcd (n,10) = 1$ tiene un múltiplo que puede ser escrito con sólo el dígito $9$ .

usuario2993422 ( http://math.stackexchange.com/users/212041/user2993422 ), prueban que hay infinitos números de la forma $x = 111....1$ de tal manera que $31|x$ URL (versión: 2015-06-13): prueban que hay infinitos números de la forma $x = 111....1$ de tal manera que $31|x$

Answer 3

111....111 - 11111....111 = 1111....11000....000 = 1111...1* $10^m$ .

$ \gcd (2017, 10^m) = 1$

Así que la declaración equivale a mostrar $2017|1111....1$ para unos 1111.... 1.

El 2017 es el año principal.

Así que basta con mostrar $p|111....1$ para unos 1111..11 por cada primo $p$ .

$10^{p-1} \equiv 1 \mod p$ por el pequeño teorema de Fermat. Así que $p|10^{p-1}- 1.

Ahora $(10^{p-1} - 1)/(10 - 1) = \sum_ {j=0}^{p-2} 10^i$ = 1111.... 1 con $p-1$ 1s.

Así que $p| \frac {10^{p-1} - 1}{10 -1}*9$ . Si $p \ne 3$ el $ \gcd (p,9) =1$ y $p| \frac {10^{p-1} - 1}{10 -1}$ . (Si $p = 3$ entonces $3|111$ .)

Así que $2017|(10^{2016} - 1)/9$ que es de 2016 1s.

So.... N = 111111111...1111 con con $k > 2016$ 1s y M = 11111.... 111 con $k - 2016$ 1s. es tal que N-M = 111.... 1111000..... 0 que tiene 2016 1s y k-2016 0s. Esto es divisible por 1111.... 1111 con 2016 0s que es divisible por 2017.