| Solution by Richard K. Guy, University of Calgary, and John Selfridge,
Northern Illinois University, DeKalb.
The result can be found in a fairly famous paper [3] which deserves to
be even more famous. It also appears as a special case in [2]; see the
entry 4375 in Col. 7 opposite N = 1 in Table 4 on p. 188. For our
solution, it is essential to know a little elementary number theory;
there's more than enough in section 2.8 of [4]. It is also very useful
to have access to [1] and the extension and updates circulated by
Wagstaff. The solution appears to demand formidable calculations, but
there are ways to circumvent these, some of which will be indicated
below. See the Remark on Calculation on p. 100 of [4].
If y >= 0, then x >= 1 and we can write the given equation as
6(3^(x-1) - 1) = 7(5^y - 1). (1)
If y > =, then 7 | (3^(x-1) - 1) and 6 | (x-1).
The last sentence can be expressed by saying that 3 is a primitive root
of 7. If you were born, as one of us was, before Abel and Galois, and
don't know any group theory, then this is a good way to begin to learn
some. The primitive root 3 generates the (cyclic) multiplicative group
of nonzero residues, modulo 7:
exponent e 0 1 2 3 4 5 6 ...
3^e mod 7 1 3 2 6 4 5 1 ...
The order of 3 and 5 (the other primitive root mod 7) is 6 (= phi(7)),
the order of 2 and 4 is 3, that of 6 is 2, and that of 1 is 1.
Lemma 2.31 of [4] states that if a has order h mod m, then the positive
integers k such that a^k = 1 mod m are precisely those for which h | k.
Theorem 2.40 is that if p is an odd prime and g is a primitive root
modulo p^2, then g is a primitive root modulo p^a for a = 3, 4, 5, ...
Euler's generalization of Fermat's "little" theorem states that
gcd(a,m) = 1 implies a^phi(m) = 1 mod m.
[Note that phi(p^a) = p^(a-1) (p-1).]
Before we interrupted ourselves, we had just seen that 6 | (x-1). In
fact,
x = 7, y = 4
is a solution, and we will show that there are no others. Write
equation (1) as
2 * 3^7 (3^a-1) = 7 * 5^4 (5^b-1) (2)
where a = x-7 and b = y-4. We will obtain a contradiction by assuming
that a and b are positive. Conveniently, 3 and 5 are primitive roots
of each other and of each other's squares, and hence, by the theorem
quoted above, of all higher powers.
exponent e 0 1 2 3 4 5 6 ...
5^e mod 3^2 1 5 7 8 4 2 1 ...
exponent e 0 1 2 3 4 5 10
3^e mod 562 1 3 9 2 6 18 24 (which is congruent to -1)
(a) From (2), 5^4 || (3^a-1), so 4*5^3 | a and 5^3 || a.
[We use the symbol || for "exactly divides" in the sense that 5^4
divides 3^a-1 but 5^5 does not divided 3^a-1, so 5^3 divides a, but 5^4
does not divide a.]
(b) 3^7 || (5^b-1), so 2*3^6 | b and 3^6 || b.
(c) From (a) 2^4 | (3^4-1) | (3^a-1), so 2^5 | (5^b-1) and 8 | b.
(d) From (b) & (c) 24 | b, so 390001 | (5^12+1) | (5^b-1) and 390001 |
(3^a-1) implies that 625 | a. But this contradicts (a).
End of proof. You may have a couple of objections: that the
calculations in (d) are beyond the capabilities of your hand
calculator, and where did 390001 come from? We admit that it's very
useful to have the tables [1]. But the calculations are easy: the
prime
390001 = 1 + 5^4 (5^4-1) = 1 - 5^4 + 5^8 = (5^12+1) / (5^4+1)
divides 5^b-1 = 5^(24k) - 1 which is a multiple of 5^24-1 =
(5^12-1)(5^12+1). We also want to check that the order of 3 modulo
390001 is divisible by 625. Work in the scale of 625 = 5^4 (note that
5^8 = 5^4-1 and 5^12 = -1 mod 390001): 3^6 = 5^4 +104 and we already
know that 2*3^7 = 7*5^4-1, leading to 3^13 = 55*5^4-56 and squaring and
multiplying (which can be done by hand calculation or a hand
calculator) lead eventually to 3^4875 is congruent to 91*5^4-185 which
is not congruent to 1, but whose fifth power is.
References.
[1] John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman &
S. S. Wagstaff, Factorizations of b^n +/- 1, b = 2, 3, 5, 6, 7, 10, 11,
12 up to high powers, Contemporary Math. 22, Amer. Math. Soc., Second
edition 1988 & updating by S. S. Wagstaff.
[2] R. K. Guy, C. B. Lacampagne & J. L. Selfridge, Primes at a glance,
Math. Comput. 48 (1987) 183-202.
[3] D. H. Lehmer, On a problem of Stormer, Illinois J. Math., 8 (1964)
59-79.
[4] Ivan Niven, Herbert S. Zuckerman & Hugh L. Montgomery, An
Introduction to the Theory of Numbers, Wiley, Fifth edition, 1991.
|