Associated Topics || Dr. Math Home || Search Dr. Math

### Determining Factors of a 3998-digit Number

```
Date: 08/11/99 at 01:31:43
Subject: Determining Factors of a 3998-digit Number

Dear Dr. Math

I started this problem and I have 3 of the 4 integers needed to
complete it. Can you help me?

Let N = 111...1222...2, where there are 1999 digits of 1 followed by
1999 digits of 2. Express N as the product of four integers, each of
them greater than 1.

I first did some experimentation with smaller cases.  This is what I
found using MAPLE.

> ifactor(1122);
(2) (3) (11) (17)
> ifactor(111222);
2
(2) (3)  (37) (167)
> ifactor(11112222);
(2) (3) (11) (101) (1667)
> ifactor(1111122222);
(2) (3) (7) (41) (271) (2381)

> ifactor(111111222222);
2
(2) (3)  (7) (11) (13) (37) (166667)
> ifactor(11111112222222);
(2) (3) (47) (239) (35461) (4649)
> ifactor(1111111122222222);
(2) (3) (11) (19) (73) (101) (137) (739) (1187)
> ifactor(111111111222222222);
3
(2) (3)  (37) (43) (983) (333667) (3943)
> ifactor(11111111112222222222);
(2) (3) (11) (41) (271) (1666666667) (9091)
> ifactor(1111111111122222222222);
(2) (3) (7) (1543) (1543067) (513239) (21649)
> ifactor(111111111111222222222222);
2
(2) (3)  (7) (11) (13) (37) (101) (166666666667) (9901)
> ifactor(11111111111112222222222222);
(2) (3) (53) (79) (265371653) (328121) (2287) (2221)

Since the number is even, 2 is always one of the factors. I think it
should be possible to analyze the cases and show that 3 is always a
factor. I can see why 11 is a factor if the number of 1's is even. In
the case that I am interested in, maybe I can show that 7 is a factor.
Then since 2, 3, and 7 are prime numbers, if each one is a factor
separately, their product must be a factor, and the final factor is
what is left over. I'm sorry but I can't figure out what the other

Sincerely,
```

```
Date: 08/21/99 at 16:44:14
From: Doctor Twe
Subject: Re: Determining Factors of a 3998-digit Number

There are some shortcuts to see if a number is evenly divisible by
certain integers. You've already mentioned one: If the value is even
(ends in 0, 2, 4, 6, or 8), it is divisible by 2.

Here are some others:

- If the sum of the digits is a multiple of 3 (3, 6, 9, 12...), the
number is divisible by 3. (This can be done recursively - that is,
if the sum of the digits of the sum of the digits is a multiple of
3, the number is divisible by 3, etc.)

- If the value of the last two digits is divisible by 4, the number
is divisible by 4. (For example, 7876 is divisible by 4 because
76/4 = 19.)

- If the number ends in 5 or 0, it is divisible by 5.

- If the number is divisible by 2 and 3 (as tested by the methods
above), it is divisible by 6.

- If the value of the last three digits is divisible by 8, the number
is divisible by 8. (For example, 9336 is divisible by 8 because
336/8 = 42.)

- If the sum of the digits is a multiple of 9 (9, 18, 27...), the
number is divisible by 9. (This can be done recursively - that is,
if the sum of the digits of the sum of the digits is a multiple of
9, the number is divisible by 9, etc.)

- If the number ends in 0, it is divisible by 10.

- There is a "test" for divisibility by 7 as well, but it would be
pretty complicated to apply to your number. It goes like this:
Beginning with the leftmost digit, multiply each digit by 3 and add
the next digit. Multiply the result by 3 and add the next digit,
etc. If the final sum is a multiple of 7, then the original number
is a multiple of 7. For example, 8162 is divisible by 7 because
[(8*3+1)*3+6]*3+2 = 245, which is 7*35. (You could re-apply the rule
to test 245 if you weren't sure.)

- There is a similar rule for 11: Beginning with the leftmost digit,
negate each digit (reverse the sign, or multiply it by -1) and add
the next digit. Negate the result and add the next digit, etc. If
the final sum is a multiple of 11, the original number is a multiple
of 11.

Using these shortcuts we can confirm that your number is indeed a
multiple of 2 (it's even) and 3 (since there are the same numbers of
1's and 2's in the number, each 'pair' adds to 3). We can also quickly
see that 4, 5, 8 and 11 won't work. (With 11, the first 1998 1's add
to 0 using the method; then the next steps would be -(1)+2 = 1,
-(1)+2 = 1, etc. We can see that this would end in 1.)

I'm not sure of a way to "shortcut the shortcut" for 7's, but if 7
indeed works, then the final factor is simply N/(2*3*7).

If I come up with another way to figure out the third factor (whether
or not it's 7), I'll let you know!

- Doctor TWE, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 09/13/1999 at 18:49:35
From: Doctor Twe
Subject: Re: Determining Factors of a 3998-digit Number

Note: For the purposes of this discussion, I'll use the following
notation: 1..{4}..1  =  111111 (i.e., the number in braces {} is the
number of repetitions NOT counting the end ones shown).

I thought some more about your problem and came up with more ideas.
First, 7 is NOT a factor. In order to see why, let's look at a simpler
example. Suppose that we wanted to see if 7 was a factor of 141,435.
This is the same as asking if 141,435 is a multiple of 7. Is there
some value x such that 7*x = 141,435 ?  We can break this into parts.
We know that 7*2 = 14, so 7*20,000 = 7*2*10,000 = 140,000. Likewise,
7*200 = 7*2*100 = 1,400.  Finally, we know that 7*5 = 35. Why did we
pick these values? Because we saw that the number 141,435 started with
a 14... (which we recognized as a multiple of 7). So:

141,435 =   140,000 =   7*2*10,000
+   1,400 = + 7*2*   100
+      35 = + 7*5*     1

We now know that the top number (7*2*10,000) is a multiple of 7, the
second number (7*2*100) is a multiple of 7, and the bottom number
(7*5) is a multiple of 7. Since our original number, 141,435 is the
sum of these numbers, it, too, must be a multiple of 7. Algebraically,
7*x+7*y+7*z = 7*(x+y+z).

Using this strategy, we can "remove" the 14 from the front. 141,435 is
a multiple of 7 only if 1,435 is a multiple of 7. Then we can "remove"
the next 14. 1,435 is a multiple of 7 only if 35 is a multiple of 7.
We could do this for larger numbers, too - which we'll need to do for
the problem you sent us, as follows:

Since 111111 = 15873 * 7, i.e. 111111 is a multiple of 7, thus
1111110..{n}..0 = 158730..{n}..0 * 7, and is also a multiple of 7. So
if 1111111..{1991}..12..{1997}..2 (your number N) is divisible by 7,
then

-  1111110........{3990}........0   (a multiple of 7)
------------------------------
1..{1991}..12..{1997}..2

must also be a multiple of 7. Similarly, if 1..{1991}..12..{1997}..2
is divisible by 7, then

1111111..{1985}..12..{1997}..2   (the previous step's value)
-  1111110........{3984}........0   (a multiple of 7)
------------------------------
1..{1985}..12..{1997}..2

must also be a multiple of 7. We can continue to "remove" groups of
six 1's in this manner. After 333 such removals, we come to the
conclusion that 12..{1997}..2 must be a multiple of 7.

Since 12222 = 1746 * 7, i.e. 12222 is a multiple of 7, thus
122220..{n}..0 = 17460..{n}..0 * 7, and is also a multiple of 7. So if
12..{1997}..2 (the previous step's value) is divisible by 7, then

122222..{1993}..2   (the previous step's value)
-  122220..{1993}..0   (a multiple of 7)
------------------------------
2..{1993}..2

must also be a multiple of 7.

Since 222222 = 31746 * 7, ie. 222222 is a multiple of 7, thus
2222220..{n}..0 = 317460..{n}..0 * 7, and is also a multiple of 7. So
if 2..{1993}..2 (the previous step's value) is divisible by 7, then

2222222..{1987}..2   (the previous step's value)
-  2222220..{1987}..0   (a multiple of 7)
------------------------------
2..{1987}..2

must also be a multiple of 7. We can continue to "remove" groups of
six 2's in this manner. After 332 such removals, we come to the
conclusion that 222 must be a multiple of 7. But clearly 222 is not a
multiple of 7, so neither is your original number N.

Whew!

I discussed your problem with my wife, and she came up with the
obvious (AFTER you think of it) third factor. She said "wouldn't
1..{1997}..1 be a factor?" Of course! It goes into the "front half"
once, and the "back half" twice. So N / 1..{1997}..1 = 10..{1996}..02.
The fourth factor, then, becomes 10..{1996}..02 / 6.  The division
isn't too difficult because of the repeated digits in the middle. I'll
leave it to you to finish it, but write back if you get stuck.

A final note: I didn't check whether or not the third and fourth
factors are primes. If either one is not prime, there are other
possible solutions.

Good luck!

- Doctor TWE, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search