Three numbers in pairs produce the Highest common factors of A million and four, A million and six and A milliion and 8, but this is not possible. why?

Question

Three positive integers are written on a whiteboard. David calculated the highest common factor of two of them and obtained 1000004. Rose and Stephen did the same obtaining 1000006 and 1000008 respectively. Emily is sre at least one of her friends made a mistake despite the fact that they calculated the Highest common factors of different pairs of numbers. Is she right? and why?

Answer 1

Well, if you know how to solve the RSA security problem (see Wikipedia), this simple math problem is a piece of cake!

O.K. three numbers A,B,C have pairs:   A,B;   B,C;  and A.C      (order of elements in sets is not important)

The GCF (greatest common factor), or HCF, is the greatest factor that evenly divides two numbers.

So, we factor:

     (D):  1000004  yields    2, 2, 53, 53, 89

      (R):  1000006 yields     2, 7, 7, 71429

      (S):  1000008 yields    2, 2, 2, 3, 3, 17, 19, 43

At this point, I might agree with Emily that at least one of her friends made a mistake.  I think this because most simple math problems use only “magic numbers” that don’t have messy fractions or make difficult calculations (since I may not be allowed to use a calculator or a computer).

Thus, Rose says that two of the numbers can be divided by 2, but not by 4 (see the factor list), but David insists that two of the numbers can be divided by 4 (see his factor list).  However, there are only three numbers, so this is impossible.

Now if Rose made a miscalculation (see 71429) then she might have two numbers that can be divided by 4.  Then, that leaves other factors that must appear or not appear in sets of two numbers  (Hey, this reminds me of the Master Mind game!).

 

       

Answer 2

Let's call the 3 numbers A, B, and C

 

- The greatest common factor (GCF) of A and B is 1000004

- The GCF of B and C is 1000006

- The GCF of C and A is 1000008

 

So you can say the following:  Since 1000004 is a common factor of A and B, each can be written as a multiple of of 1000004:

 

A = 1000004 K
B = 1000004 L

 

K and L are each some integer.  And you know that they have NO common factors, or else you could factor out that factor and multiply it by 1000004 and you would get a GREATER common factor for A and B.  But since 1000004 is the GREATEST common factor of A and B, you can't do that.  So K and L can't have any common factors.

 

So using the same logic, you can say that:

 

B = 1000006 M
C = 1000006 N

 

where M and N have no common factors, and:

 

C = 1000008 P
A = 1000008 Q

 

where P and Q have no common factors.

 

Now, notice that all the GCF's are even.  Therefore you can factor out a 2 in each set of expressions:

 

A = 1000004 K = 2K * 500002
B = 1000004 L = 2L * 500002

B = 1000006 M = 2M * 500003
C = 1000006 N = 2N * 500003

C = 1000008 P = 2P * 500004
A = 1000008 Q = 2Q * 500004

 

You can even go further with two of the groups:

 

A = 2² K * 250001
B = 2² L * 250001

C = 2² P * 250002
A = 2² Q * 250002

 

But you can't do that for the other group, so you still have:

 

B = 2M * 500003
C = 2N * 500003

Now look at B and C.  Either M is odd, or N is odd.  If they were both even, then you'd be able to factor out another 2 from them both, and you'd end up with a common factor for B and C of 2² * 500003 = 2000012.  But since 1000006 is the GREATEST common factor of B and C, that's impossible.  So one of M or N is odd. 

 

Let's just suppose that M is the one that's odd. Therefor B = 2 * (odd number) * 500003, which means that in the prime factorization of B, there is only one power of 2.

 

But earlier, we showed that B = 2² L * 250001, which means that the factorization of B has 2² in it.  So that's a contradiction.

 

In the same way, we could suppose that N is odd, and we would get another contradiction.  So by starting with the statements about the GCF's we end up with an impossible situation.  That means that one of the students made a mistake.

 

Now...  There may be an easier way to do this!  I'd be interested to see if anyone has one.