Subscribe via feed.

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.

This post is under “MathsChallenge” and has 13 respond so far.

13 Responds so far- Add one»

1. 1. Karys Said：

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

6N = 6*N6

N6 = 1016949152542372881355932203389830508474576271186440677966
with 57 digits.

2. 2. Chris Said：

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.

3. 3. cazayoux Said：

Help me to understand.
How do you solve this?

4. 4. Chris Said：

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*10n + N
=> 59N +36 = 6*10n
=> 6*10n = 36 (mod 59)

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

5. 5. Karys Said：

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.

6. 6. Chris Said：

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.

7. 7. Chris Said：

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*10n + N
=> 59N +36 = 6*10n
=> 6*10n = 36 (mod 59)
Multiplying both sides by 10 => 60*10n = 360 = 6*60 (mod 59)
=> 10n = 6 (mod 59)
(could have got that by dividing by 6 – that’s allowed because 59 is prime)
Multiplying both sides by 10 again => 10n+1 = 60 = 1 (mod 59)

Fermat’s little theorem (FLT) says 1058 = 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
102 = 1 (mod 59), and that is false
or
1029 = 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 “Little 6″.

Now substitute 57 for n in 59N = 6*10n – 36 => 59N = 6*1057 -36
= 5999999999999999999999999999999999999999999999999999999964

So N = 101694915254237288135593220338983050847457627118644067796
and the required number is N:6 = 10N + 6 =
1016949152542372881355932203389830508474576271186440677966
Check
6*1016949152542372881355932203389830508474576271186440677966
= 6101694915254237288135593220338983050847457627118644067796
as required.

Aside: If ap-1 = 1 (mod p), where p is prime and gcd(a,p) = 1,
Then a(p-1)/2 = ±1 (mod p).
Proof: if x2 = 1 (mod p), then x2 – 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)

8. 8. Chris Said：

Karys brought up the Little x generalisation. For that we have
x*N:x = x:N => (10x-1)N +x2 = x*10n
and then x*10n = x2 (mod 10x-1)
Multiply by 10 => 10x * 10n = 10 x2 (mod 10x – 1)
=> 10n = x (mod 10x – 1), using 10x = (10x -1) + 1 = 1 (mod 10x – 1)
Multiplying by 10 again => 10*10n = 10x (mod 10x – 1)
=> 10n+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 x2. 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

```x = 2 => 1018 = 1 (mod 19) => n = 17
x = 3 => 1028 = 1 (mod 29) => n = 27
x = 4 => 10 6 = 1 (mod 39) => n =  5
x = 5 => 1042 = 1 (mod 49) => n = 41
x = 6 => 1058 = 1 (mod 59) => n = 57
x = 7 => 1022 = 1 (mod 69) => n = 21
x = 8 => 1013 = 1 (mod 79) => n = 12
x = 9 => 1044 = 1 (mod 89) => n = 43
```

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

9. 9. Chris Said：

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

10. 10. Chris Said：

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.

11. 11. Karys Said：

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.

12. 12. Chris Said：

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.

13. 13. Chris Said：

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)

PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0