My Math Forum Least integer having all digits 4 divisible by 169

 Number Theory Number Theory Math Forum

 May 24th, 2011, 04:26 PM #1 Senior Member   Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0 Least integer having all digits 4 divisible by 169 (Olimpíada de Mayo, 2010) - Find the smallest integer of the form 4444.. (all digits 4) which is divisible by 169. My progress: If k is the number of digits in the number, then obviously $10^{k} \eq 1 (mod 13)$, so it can be found that k must be divisible by 6. Using any computational tools, it is readily shown that k = 78, but since this is an olympiad question, it should be done by hand. Should I list all the possibilities for mod 169, for k = 6, 12, ... 78? There should be a simpler way. Additional question: Is it possible to define the length of the period of $10^{k} (mod p)$ for any p without listing the remainders?
 May 24th, 2011, 08:47 PM #2 Newbie   Joined: May 2011 Posts: 19 Thanks: 0 Re: Least integer having all digits 4 divisible by 169 $44\ldots 44= 4\cdot 11\ldots 11$ and $13^2$ divides it only if $13^2$ divides $11\ldots 11= (10^k-1)/(10-1)$ and $13^2$ divides that only if $13^2$ divides $10^k-1$, so $10^k\equiv 1 \pmod {13^2}$. Euler's totient $\varphi(13^2)= 12 \cdot 13$ so $k$ is the smallest divisor $k|2^2 \cdot 3 \cdot 13$ such that $10^k\equiv 1 \pmod {13^2}$. There are $8$ possibilities to check in order of size: * $10^1 \equiv 10 \pmod {13^2}$ * $10^2 \equiv 100 \pmod {13^2}$ * $10^{2^2} \equiv 29 \pmod {13^2}$ * $10^{2\cdot 3} \equiv 27 \pmod {13^2}$ * $10^{2 \cdot 13} \equiv 22 \pmod {13^2}$ * $10^{2 \cdot 3 \cdot 13} \equiv 1 \pmod {13^2}$ we stop here because we found the answer.
 May 25th, 2011, 08:30 AM #3 Senior Member   Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0 Re: Least integer having all digits 4 divisible by 169 Thanks! so I guess that this is true: $a^{\varphi(n)} \eq 1 (mod n) \text \ {implies} a^{\frac{\varphi(n)}{m}} \eq 1 (mod n) \ \text{if} m|\varphi(n)$
 May 25th, 2011, 09:11 AM #4 Senior Member   Joined: Apr 2011 From: Recife, BR Posts: 352 Thanks: 0 Re: Least integer having all digits 4 divisible by 169 Sorry, my last post's statement is obviously wrong. But why must k be a divisor of phi(13^2) so that 10^k is congruent to 1 modulo 13²?
 May 25th, 2011, 09:42 AM #5 Math Team   Joined: Apr 2010 Posts: 2,780 Thanks: 361 Re: Least integer having all digits 4 divisible by 169 The period repeating decimals of 1/169 is 78. I think that too indicates that the amount of 4's is 78. http://en.wikipedia.org/wiki/Repeating_ ... rime_to_10
May 25th, 2011, 05:38 PM   #6
Newbie

Joined: May 2011

Posts: 19
Thanks: 0

Re: Least integer having all digits 4 divisible by 169

Quote:
 Originally Posted by proglote Sorry, my last post's statement is obviously wrong. But why must k be a divisor of phi(13^2) so that 10^k is congruent to 1 modulo 13²?
It's a consequence of group theory (Lagrange's theorem). The order of an element $a$ is the smallest natural number $o$ such that $a^o \equiv 1 \pmod n$, every element $\pmod n$has order dividing $\varphi(n)$.

 Tags 169, digits, divisible, integer

### smallest integer 4444

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post gelatine1 Algebra 4 January 7th, 2013 09:39 PM harrypham Number Theory 9 July 26th, 2012 08:29 PM CarpeDiem Elementary Math 7 July 13th, 2012 07:35 PM jamesb1 Number Theory 3 November 3rd, 2011 02:01 PM CRGreathouse Number Theory 11 December 26th, 2006 10:38 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top