## Little 6

Posted by Chris on March 22, 2012 – 10:01 pm

Here’s a variation on a golden oldie. It was a very similar problem that got me hooked on ToM and caused me to learn about modulo arithmetic. Hey, it’s this or nothing.

What is the smallest positive integer that ends with a 6, becomes 6 times as large when the 6 is moved to the start.

e.g. I want something along the lines of: 6123 = 6*1236.

~~You’ll find that the Windows calculator could be useful for this problem.~~

You’ll find http://www.wolframalpha.com useful for the calculations.

March 23rd, 2012 at 11:58 am

Love those I remember the 3*N = N3 one so solved that one easily.

6N = 6*N6

The answer is

N6 = 1016949152542372881355932203389830508474576271186440677966

with 57 digits.

March 23rd, 2012 at 12:34 pm

Hi Karys, You got it. Did you prove that there isn’t a smaller number?

It’s 58 digits, count ‘em.

Sorry folks, the Windows calculator isn’t good enough. Fortunately http://www.wolframalpha.com can handle it.

I love these too. I just find it amazing that the answer is so ridiculously huge.

March 23rd, 2012 at 1:54 pm

Help me to understand.

How do you solve this?

March 23rd, 2012 at 3:01 pm

Hi cazayoux. Here’s the start of my prepared solution. It will leave you with plenty to work out for yourself.

Let N be a digit string consisting of n characters. We want to solve

6*N:6 = 6:N, where : denotes string catenation.

The number we want is N:6

Now consider N to be a number. We want to solve for n

6(10N + 6) = 6*10

^{n}+ N=> 59N +36 = 6*10

^{n}=> 6*10

^{n}= 36 (mod 59)…

Now think about Fermat’s little theorem, and force that last equation into a suitable form. …

March 24th, 2012 at 5:52 am

I did brute force a bit although some arithmetic could do it, to prove it’s the smallest.

6(10^n -6) = 59N

Try all n beginning from 0 until 59 divides 10^n-6 (59 and 6 are coprime so 59 divides the other factor). You get the number of digits of the smallest and the formula proves there’s only one with this many digits.

I notice that there could not necessarily have been any solution (like if we used another number instead of 6 or maybe I didn’t see something) and if there’s one there’s infinitely more, as Fermat’s theorem states in this case that

10^58 = 1 (59), so as long as n=57+58*k with any k>0 you can calculate the solution.

PS Yes indeed there was a mistake… to count exactly how many digits there are in N, I look at log_10 N = (ln N)/(ln 10) and add 1. I forgot to add 1.

March 24th, 2012 at 11:48 am

Hi Karys. I knew it was 58 because n = 57 is the length of N, and we have the trailing 6, taking us to 58. I nearly added the bit about the next highest etc., solutions.

Thanks for mentioning the “Little x” idea. I’ve nearly written that one up. It brings out a number of interesting matters. I’ll wait a little longer before posting it.

March 25th, 2012 at 10:51 am

Here’s my prepared solution.

Let N be a digit string consisting of n characters. We want to solve

6*N:6 = 6:N, where : denotes string catenation.

The number we want is N:6

Now consider N to be a number. We are going to find n.

6(10N + 6) = 6*10

^{n}+ N=> 59N +36 = 6*10

^{n}=> 6*10

^{n}= 36 (mod 59)Multiplying both sides by 10 => 60*10

^{n}= 360 = 6*60 (mod 59)=> 10

^{n}= 6 (mod 59)(could have got that by dividing by 6 – that’s allowed because 59 is prime)

Multiplying both sides by 10 again => 10

^{n+1}= 60 = 1 (mod 59)Fermat’s little theorem (FLT) says 10

^{58}= 1 (mod 59), but it doesn’t guarantee the 58 is the smallest power that does that trick.58 = 2*29. The only possibilities for a smaller power are

10

^{2}= 1 (mod 59), and that is falseor

10

^{29}= 1 (mod 59), and that is false also (it actually gives -1).(see the aside at the end).

So 58 is in fact the smallest power. So n+1 = 58 => n = 57. So N is 57 digits long. Hence the joke title “

Little6″.Now substitute 57 for n in 59N = 6*10

^{n}– 36 => 59N = 6*10^{57}-36= 5999999999999999999999999999999999999999999999999999999964

So N = 101694915254237288135593220338983050847457627118644067796

and the required number is N:6 = 10N + 6 =

1016949152542372881355932203389830508474576271186440677966

Check

6*1016949152542372881355932203389830508474576271186440677966

= 6101694915254237288135593220338983050847457627118644067796

as required.

–

Aside: If a

^{p-1}= 1 (mod p), where p is prime and gcd(a,p) = 1,Then a

^{(p-1)/2}= ±1 (mod p).Proof: if x

^{2}= 1 (mod p), then x^{2}– 1 = 0 (mod p) =>(x-1)(x+1) = 0 (mod p). As p is prime, neither x-1 nor x+1 can divide it, so

either x-1 = 0 (mod p) => x = 1 (mod p)

or x+1 = 0 (mod p) => x = -1 (mod p)

March 25th, 2012 at 11:28 am

Karys brought up the Little x generalisation. For that we have

x*N:x = x:N => (10x-1)N +x

^{2}= x*10^{n}and then x*10

^{n}= x^{2}(mod 10x-1)Multiply by 10 => 10x * 10

^{n}= 10 x^{2}(mod 10x – 1)=> 10

^{n}= x (mod 10x – 1), using 10x = (10x -1) + 1 = 1 (mod 10x – 1)Multiplying by 10 again => 10*10

^{n}= 10x (mod 10x – 1)=> 10

^{n+1}= 1 (mod 10x -1)Aside: thanks Karys, I wouldn’t have noticed that “universal” solution if you hadn’t brought the idea up. I also note that I could have divided by x rather than the safer multiply by 10. Generally, division isn’t definable with non prime mods. There is something special going on here. It might simply be because x is a factor of x

^{2}. I might have a think about that.So, if FLT worked for all the mods, we’d nominally have that

n + 1 = 10x – 2 => n = 10x – 3. But life isn’t that simple.

x = 4 and x = 7 give non-primes, so we need Euler’s generalisation of FLT (or Carmichael’s enhancement of Euler’s generalisation).

For x = 4 we get 39 = 3*13, and φ(39) = 39(1 – 1/3)(1 – 1/13) = 24

For x = 7 we get 49 = 7*7, and φ(49) = 49(1 – 1/7) = 42 (oh boy!)

Even Euler (and Carmichael) don’t guarantee the smallest power. If there is a smaller power it must be a factor of the one we’ve got. Skipping the boring details, we end up finding

I won’t bother writing down the long numbers those lead to.

March 25th, 2012 at 6:06 pm

If a x = b x (mod m) and gcd(x,m) = 1, then Euler’s little theorem =>

x

^{φ(m)}= 1 (mod m)Multiplying both sides of the first equation by x

^{φ(m)-1}=> a x x

^{φ(m)-1}= b x x^{φ(m)-1}(mod m)=> a x

^{φ(m)}= b x^{φ(m)}(mod m)=> a = b (mod m)

So division is OK as long as we divide by whole factors that are coprime to m.

In the last post, I could have directly divided by x, because gcd(x,10x-1) = 1

March 25th, 2012 at 6:48 pm

I’m a plonker.

If ax = bx (mod m) then (a-b)x = 0 (mod m)

So either a = b (mod m) or x = 0 (mod m)

We

~~only~~require~~gcd(x,m) < m, rather than~~gcd(x,m) = 1 in order to be able to divide by a whole factor.March 26th, 2012 at 1:50 pm

actually, with y = (a-b)

if xy = 0 (m)

then

IF m is prime then x=0(m) or y=0(m)

IF m is coprime to x (respectively y…) then y=0(m) (resp…) (the ‘m is prime’ is a particular case of this)

ELSE in general if m is composite you can’t conclude on that,

e.g.

x = 6 = 3*2,

y = 35 = 5*7,

m = 21 = 3*7,

m divides neither x or y.

The general rule you will want to use is when m is coprime to x (I mean gcd(x,m)=1).

For example modulo (10x-1), you can always ‘divide’ by x as it is coprime to (10x-1). ‘divide’ by x means to multiply by its (one and only) inverse, in the ring of modulo remainders (however you call that), which is exactly 10. (10x=1(10x-1))

So when you multiplied by 10, what you really did as you can see is divide by x.

It surprised me that there is in fact always a solution but now it seems quite obvious since you have done all the work.

I find this to be a fun problem of arithmetics and group theory, and the solution is just ridiculously big.

March 26th, 2012 at 3:56 pm

Hi Karys. Although I had been saying divide, that was misleading. It would have been better to say cancelling.

I agree, if xy = 0 (mod m), then we can only safely conclude that

x = 0 (mod m) if gcd(y,m) = 1 and vice versa. Thank you.

Division would mean e.g. find b if b = 3/7 (mod 11)

Because 11 is prime that can be solved. There are several ways of doing that.

e.g. 7b = 3 (mod 11) => 18b = 3 (mod 11) => 6b = 1 (mod 11)

=> 12b = 2 (mod 11) => b = 2 (mod 11)

Check, replace b with 2 => 2 = 3/7 (mod 11)

multiply by 7 => 14 = 3 (mod 11) and that’s true.

You’ll also find that no other solution exists.

An example of the problem of division.

5*1 = 5*3 = 5*5 = 5*7 = 5*9 = 5 (mod 10)

So seem to have that 5/5 = 1 = 3 = 5 = 7 = 9 (mod 10)

Clearly hopeless, but multiplying by 5 => 5(5/5) = 5… (mod 10) at least.

March 27th, 2012 at 8:12 am

Here’s an an example of what saying division is well defined with prime mods.

Let x = 1/7 (mod 11) => 7x = 1 (mod 11) => x = 8 (mod 11)

I found that by trial and error.

Now consider e.g. b = 3/7 = 3(1/7) = 3*8 = 24 = 2 (mod 11)

Just as I found in my last post.

In fact we’ll end up with, for n/7 (mod 11) as n goes from 1 to 11

8,5,2,10,7,4,1,9,6,3,0

So we have unique and well defined meaning for divide by 7 (mod 11)