The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Number Theory: Primes

Date: 07/10/2003 at 04:23:10
From: Carlos
Subject: Number theory

Find all primes p,q such that ((7^p-2^p)(7^q-2^q))/(pq) is an integer.

If p divides (7^p-2^p)(7^q-2^q), then p divides either (7^p-2^p) or 
(7^q-2^q) and vice versa. It can easily be deduced from Fermat's 
Little theorem that 7^p - 2^p = 5 (mod p). Thus p divides (7^p-2^p) 
iff p = 5.

From this I have figured that (p=5,q=5),(p=5,q=11),(p=5,q=61) are 
all solutions. Where I get stuck is for the case 7^q=2^q mod p and 
7^p=2^p mod q. I wonder if 7^q=2^q mod p and 7^p=2^p mod q have any 
solutions. I suspect that for p (not 5) to divide (7^q-2^q), p > q. 
This will prove that there are no other solutions. But I cannot 
prove this assertion.

Date: 07/10/2003 at 04:43:59
From: Doctor Jacques
Subject: Re: Number theory

Hi Carlos,

You are on the right track.

Assume that 7^p = 2^p (mod q) with p and q primes, and q <> 5. As q is 
obviously odd, 2 has an inverse mod q, namely:

  a = (q+1)/2

and we may write:

  (7a)^p = 1 (mod q)

Now, the order of (7a) mod q is either 1 (in which case q = 5) or p, 
and divides (q - 1), by Fermat's theorem. This should allow you to 
use your idea to conclude the proof.

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum 
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.