[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1911.0. "Open number theory problem?" by EVTSG8::ESANU (Au temps pour moi) Wed Nov 23 1994 07:58

The following problem was still open a few years ago:


	For two different primes  p  and  q , are the natural numbers

	 q              p
	p  - 1         q  - 1
	------   and   ------   relatively prime?
	p - 1          q - 1


Does anyone know whether it has been solved?

Mihai.
T.RTitleUserPersonal
Name
DateLines
1911.1No proof, but ...BIS5::VANLAER_WWillem Van laerThu Jun 15 1995 16:12371
Let p and q be two different primes, p < q.

Let P=(p^q-1)/(p-1) 	and	Q=(q^p-1)/(q-1).

Conjecture: P and Q have no common divisors.

I have have not been able to (dis)prove this. 

The following are some thoughts on the conjecture.

P and Q have some peculiar properties. Maybe some of these
may be of use to someone, in (dis)proving  the conjecture.

Greetings,

Willem Van laer



===============================================================================

Property 1
----------
There are integers p'', q'' and w such that

P=(p^q-1)/(p-1) 	= p''*p*q+1

Q=(q^p-1)/(q-1) 	= w*p*q-(q-1)		(if p | q-1)
			= q''*p*q+1		otherwise

Proof
-----
From Fermat's property: there are integers p' and q' such that

	p^(q-1)-1=p'*q	and	q^(p-1)-1=q'*p				(0)

P=1+p+p^2+p^3+...+p^(q-2)+p^(q-1)					(1)
Q=1+q+q^2+q^3+...+q^(q-2)+q^(q-1)  					(2)

P=(p^(q-1)-1)/(p-1)+p^(q-1)
Q=(q^(p-1)-1)/(q-1)+q^(p-1)

(0) in (1) and (2) gives

P=(p'*q)/(p-1)+p'*q+1=(p'*q+p'*q*(p-1))/(p-1)+1
P=(p'*p*q)/(p-1)+1							(3)
Q=(q'*p)/(q-1)+q'*p+1=(q'*p+q'*p*(q-1))/(q-1)+1
Q=(q'*p*q)/(q-1)+1							(4)

Case 1: p does not divide q-1

Left hand sides of (3) and (4) are integers, thus so are the right hand sides.
p-1 (<p<q) has no common factors with p nor q (both prime),
q-1 (q) has no common factors with p (does not divide q-1) nor q (both prime),
thus p-1 | p', let p''=p'/(p-1)
and  q-1 | q', let q''=q'/(q-1)

Thus (3) and (4) become
P=1+p''*p*q
Q=1+q''*p*q

Case 2: p divides q-1

Then there is an integer x such that q=x*p+1.

Q=((x*p+1)^p-1)/(q-1)=((x*p)^p+p*(x*p)^(p-1)+....+p*(x*p)+1-1)/(x*p+1-1)
Q=x*p*((x*p)^(p-1)+p*(x*p)^(p-2)+....+p)/(x*p)
Q=(x*p)^(p-1)+p*(x*p)^(p-2)+....+p

Which shows that Q is a multiple of p.	Q=u*p
(2) shows that Q is 1 + multiple of q.	Q=v*q+1

q=x*p+1 (because p | q-1)
Q	=v*q+1
	=v*x*p+v+1

The left hand side is a multiple of p, so must be the right hand side. 
Thus v+1 is a multiple of p. Let v=w*p-1.

Q       =v*q+1
	=(w*p-1)*q+1
	=w*p*q-(q-1)

Q.E.D.
===============================================================================

===============================================================================

Property 2
----------

All prime factors of P are of the form (1 + multiple of q).		(5)

All prime factors of Q are of the form (1 + multiple of p), if p does not 
divide q-1.								(6)

All prime factors of Q are of the form (1 + multiple of p), or equal to p, 
if p | q-1.								(7)

Proof
-----

Let n be a prime factor of P.
Then n | p^q-1.								(8)
From Fermat's property: n | p^(n-1)-1.					(9)

A well know property states that:
	let n be prime
	n does not divide p
	e is the smallest number for which n | p^e-1 holds
then
	n | p^f-1 if and only if f is a multiple of e

We apply this to (8) and (9).
Since q is prime this e can only be
	1
or	q.

e=1 implies 
	n | p-1, or p=x*n+1
	and P	=((x*n+1)^q-1)/(x*n+1-1)
		=(x*n)^(q-1)+q*(x*n)^(q-2)+...+q
	The left hand side cannot be divided by n (which is smaller then p 
	since n | p-1), since it leaves q (prime)
	as rest. This is in contradiction with n be a prime factor of P.
	So e cannot be 1.
e=q implies 
	n-1 is a multiple of q, or n is 1+ multiple of q

Which proves (5).

Let n be a prime factor of Q.
Then n | q^p-1.								(10)
From Fermat's property: n | q^(n-1)-1.					(11)

A well know property states that:
	let n be prime
	n does not divide p
	e is the smallest number for which n | p^e-1 holds
then
	n | p^f-1 if and only if f is a multiple of e

We apply this to (10) and (11).
Since p is prime this e can only be
	1
or	p.

e=1 implies 
	n | q-1, or q=x*n+1
	and Q	=((x*n+1)^p-1)/(x*n+1-1)
		=(x*n)^(p-1)+p*(x*n)^(p-2)+...+p
	The right hand side cannot be divided by n (smaller then q, 
	as n | q-1), since it leaves prime p 
	as rest, except if n=p, and p | q-1. property 1 shows that 
	p | Q if p | q-1.
e=q implies 
	n-1 is a multiple of q, or n is 1+ multiple of q

Which proves (6) and (7).
===============================================================================

===============================================================================

Property 3
----------

Let p > 2.
If p | q-1, then p divides Q only once (p | Q, but p^2 does not divide Q).

Proof
-----

Let q=xp+1

Q	=((x*p+1)^p-1)/(x*p+1-1)
	=(x*p)^(p-1)+p*(x*p)^(p-2)+...+p*(p-1)*(x*p)/2+p

Which shows that p | Q.

Q/p	=x*(x*p)^(p-2)+p*x*(x*p)^(p-3)+...+p*(p-1)*x/2+1

This shows that Q/P cannot be divided by p (leaves 1 as rest).

Q.E.D.

Note: for p=2, p can divide Q more then once:

(3^2-1)/(3-1)=4=2^2
(7^2-1)/(7-1)=8=2^3

(q^2-1)/(q-1)=q+1, which can be any power of 2.

===============================================================================

===============================================================================

Property 4
----------

If p=2, then P and Q have no common divisors.

Proof
-----

P=(2^q-1)/(2-1)=2^q-1
Q=(q^2-1)/(q-1)=q+1

From property 2, we have
divisors of P have form x*q+1
divisors of Q have form y*2+1 or 2 (because q is odd, so 2 | q-1)

2 does not divide P, so cannot be a common divisor.
So, a common divisor of P and Q has form n'*2*q+1. Since this is greater 
then Q=q+1, there cannot be a common divisor.

Q.E.D.

===============================================================================

===============================================================================

Property 5
----------

If p=3, then P and Q have no common divisors.

Proof
-----

It is sufficient to show that P and Q have no common prime divisors.

P=(3^q-1)/2
Q=q*q+q*1

If a prime number n divides Q then
	n<sqrt(Q)<sqrt(2*q*q)=q*sqrt(2)<2*q

From property 2, we have
	divisors of P have form x*q+1
	divisors of Q have form y*3+1 or 3 

3 does not divide P, so cannot be a common prime divisor.
So, a common prime divisor n of P and Q has form n'*3*q+1. 
Since this is greater then q*2 there cannot be a common divisor.

Q.E.D.

===============================================================================

===============================================================================

Property 6
----------

If P and Q have a common prime divisor n, 
then there are integer numbers n' and a such that
	n=n'*p*q+1
	P=n*(a*p*q+1)
and, if p does not divide q-1, there is an integer b such that
	Q=n*(b*p*q+1)
	P-Q=p*q*(a-b)*n


Proof.
------

Let us suppose that there is a common prime factor n of P and Q.

n cannot be equal to p, as P divided by p leaves 1 as rest (from (1)).

From property 2, we conclude that our supposition implies that n is of the form
n'*p*q+1 (since p and q are prime). This proves the first statement.

From property 2, it follows that P=n*(y1*q+1)*...*(yl*q+1) (factorisation of 
P in primes).

Thus P	=n*(Y*q+1)	(Y being an integer, Y*q+1 in general is not prime)

Let r=Y*p+1, P =(n'*p*q+1)*r

Thus	P		=n'*p*q*r+r
	p''*p*q+1	=n'*p*q*r+Y*q+1	(from property 1)
	p''*p*q		=n'*p*q*r+Y*q

The left hand side is a multiple of p, so must be the right hand side.
Since q is prime, Y must be a multiple of p. There is an integer a such that
Y=a*p.

We have P=n*r=(n'*p*q+1)*(a*p*q+1)=(n'*a*p*q+n'+a)*p*q+1.		(12)
Which proves the second statement.

From property 2, it follows that Q=n*(z1*p+1)*...*(xk*p+1) 
(factorisation of Q in primes, p is no factor of Q).

Thus Q	=n*(X*p+1)

	Let s=(X*p+1)
	Q		=(n'*p*q+1)*s
			=n'*p*q*s+s
			=n'*p*q*s+X*p+1
	q''*p*q+1	=n'*p*q*s+X*p+1 (from property 1)
	q''*p*q		=n'*p*q*s+X*p

The left hand side is a multiple of q, so must be the right hand side.
Since p is prime, X must be a multiple of q. There is an integer b such that
X=b*q.

We have Q=n*s=(n'*p*q+1)*(b*p*q+1)=(n'*b*p*q+n'+b)*p*q+1.		(13)
Which proves the third statement.

Subtracting (13) from (12) gives

	P-Q	=(n'*a*p*q+n'+a)*p*q+1 - (n'*b*p*q+n'+b)*p*q-1
		=n'*p*p*q*q*(a-b)+p*q*(a-b)
		=p*q*(a-b)*(n'*p*q+1)
		=p*q*(a-b)*n

Which proves the last statement.

===============================================================================

From the last property, I have tried - in vain - to construct a contradiction 
(showing that no such prime divisor n'*p*q*+1 exists).

The following examples show that, for some p and q, there is such a divisor 
for P or Q. Therefore, I suspect that, for suitably large p and q, there
could be a divisor n'*p*q*+1 of both P and Q. 
===============================================================================
p,q 	5 19
P,Q     4768371582031       137561

Prime divisors of 4768371582031 are 191, 6271 and 3981071.

Prime divisors of 137561 are 151 and 911.

191 (=   2 *p*q+1) divides 4768371582031
6271 (=  66 *p*q+1) divides 4768371582031
===============================================================================
p,q 	3 19
P,Q   	581130733381 381

Prime factors of 581130733381 are 1597 and 363889.
Prime factors of 381 are 3 and 127.

1597 (=  28 *p*q+1) divides     581130733
363889 (=6384 *p*q+1) divides     581130733
===============================================================================
p,q 	11 13
P,Q 	3452271214393 149346699503

Prime factors of 3452271214393 are 1093 and 3158528101.
Prime factors of 149346699503 are 23, 419, 859 and 18041.

859 (=   6 *p*q+1) divides  149346699503
===============================================================================
p,q	13 17
P,Q	720867993281778161        619036127056621

Prime factors of 720867993281778161 are 103, 443 and 15798461357509.
Prime factors of 619036127056621 are 212057 and 2919196853.

443 =   2 *  13 *  17 +1
===============================================================================
p,q	5 19
P,Q	4768371582031       137561

Prime factors of P are 191, 6271 and 3981071.
	191 =   2 *   5 *  19 +1
	6271 =  66 *   5 *  19 +1
Prime factors of 137561 are 151 and 911.
===============================================================================
1911.2HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Thu Jun 15 1995 18:5516
> Let p and q be two different primes, p < q.
> 
> Let P=(p^q-1)/(p-1) 	and	Q=(q^p-1)/(q-1).
>
> Conjecture: P and Q have no common divisors.

The first exercise (at least for me, maybe it's obvious to you!) is
to show that P and Q are indeed integers.

Let me try one.  How about (3^5-1)/2.  This is certainly an integer since
3^5 is odd, so 3^5-1 is even.  How about (5^3-1)/4.  I can calculate 5^3 is
125, so we have 124/4 which is 31.  But it's not clear to me without "doing"
it that 5^3-1 is divisible by 4.

Hmmm.

1911.3Closed form for (p^n - 1)/(p - 1)POBOXA::TSUKMichael TsukThu Jun 15 1995 19:5418
(p^n - 1)/(p - 1) can be written in closed form (for n integer) as:

sum(i = 0 to n-1) p^i = 1 + p + p^2 + p^3 + ...

If p is an integer, so is the sum.

This is usually proved in the following way:

    sum = 1 + p + p^2 + p^3 + ... + p^(n-1)
p * sum =     p + p^2 + p^3 + ... + p^(n-1) + p^n

subtracting gives:

(p - 1) * sum = p^n - 1.  Done!

But that's as far as I can get on the original problem!

				-Michael
1911.4Right math, wrong wordsEVMS::HALLYBFish have no concept of fireFri Jun 16 1995 13:418
1911.5BIS5::VANLAER_WWillem Van laerFri Jun 16 1995 14:390
1911.6please trust me. I did it myself.HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Fri Jun 16 1995 15:0371

Hi.  Please trust that the following work is something I did myself, BEFORE
reading replies .3 and .4.  I put in .2, saying that I didn't understand
why (p^q-1)/(p-1) is always an integer.

I assume that someone explained why it is, in replies .3 or .4.

But last night, after putting in my .2, while I was driving from work, I
worked out a method of proving it in my head.  I hope you'll believe me,
because this is one of those math concepts that feels important to me that
I become capable of proving and understanding without having someone else
do it for me.

Anyway, what I started thinking about is the following long division:

(oy, this is going to be painful in ascii text)


	  p^(q-1) . . .
	---------------------------------------------------------------
p - 1  )  p^q -       1
          p^q - p^(q-1)
	----------------
           p^(q-1) -  1
		 . . .

The steps shown so far are:  divide p into p^q and get p^(q-1), multiply
to get p^q - p^(q-1), subtract to get p^(q-1) - 1.

The next step, of course, is to divide again.  This time we're dividing
p-1 into p^(q-1) - 1 instead of into p^q.

I noticed that now we're dividing p-1 into a reduced-by-one power of p - 1
than we started with, and hence a pattern.

It became clear to me that what we're going to see is

	p^(q-1) + p^(q-2) + p^(q-3) ...

and that eventually, what we'll see after a future subtract is

	p^1 - 1

at which point, the remainder will be exactly 1 !

Hence the total answer is:

(p^q-1)/(p-1) = p^(q-1) + p^(q-2) + p^(q-3) + ... p^2 + p + 1

This proves it's an integer !

Let's try one example just as a sanity check:

(3^5-1)/(2-1) should equal 3^4 + 3^3 + 3^2 + 3 + 1

Left side is (81*3-1)/(2) = 242/2 = 121.

Right side is 81 + 27 + 9 + 3 + 1 = 108 + 9 + 3 + 1 = 121.

Yippee, it worked !

This proves it's an integer, but it seems to me there ought to be a more
elegant or simple way to prove it.

Now I'll read replies .3 and .4, maybe elegance du jour is presented.
But it was important to try to "do it myself" first.

Thanks.

/Eric
1911.7p = 17, q = 3313RTL::GILBERTFri Jun 16 1995 16:5325
From Richard K. Guy's "Unsolved Problems in Number Theory" (Springer-Verlag),
published in 1981.

"B25.  Bateman asks if 31 = (2^5-1)/(2-1) = (5^3-1)/(5-1) is the only prime
which is expressible in more than one way in the form (p^r-1)/(p^d-1) where
p is a prime and r >= 3 and d >= 1 are integers.  Trivially one has
7 = (2^3-1)/(2-1) = ((-3)^3-1)/(-3-1), but there are no others < 10^10.
If the condition that be be prime is relaxed, the problem goes back to
Goormaghtigh and we have the solution 8191 = (2^13-1)/(2-1) = (90^3-1)/(90-1).

   E. T. Parker observes that the very long proof by Feit and Thompson,
that every group of odd order is solvable, would be shortened if it could
be proved that (p^q-1)/(p-1) never divides (q^p-1)/(q-1) where p, q are
distinct odd primes.  In fact is has been conjectured that these two
expressions are relatively prime, but Nelson M. Stephens has observed that
when p = 17, q = 3313, they have a common factor 2pq+1 = 112643.  McKay has
established that p^2+p+1 does not divide 3^p-1 for p < 53*10^6.

P. T. Bateman and R. M. Stemmler, Waring's problem for algebraic number fields
    and primes of the for (p^r-1)/(p^d-1), Illinois J. Math.  6 (1962) 142-156.
Ted Chinburg and Melvin Henriksen, Sums of kth powers in the ring of polynomials
    with integer coefficients, Bull. Amer. Math. Soc. 81 (1975) 107-110.
A. Makowski and A. Schinzel, Sur l'equation indeterminee de R. Goormaghtigh,
    Mathesis 68 (1959) 128-142 and 70 (1965) 94-96.
N. M. Stephens, on the Feit-Thompson conjecture, Math. Comput. 25 (1971) 625."
1911.8AUSSIE::GARSONachtentachtig kacheltjesSat Jun 17 1995 02:4614
    re .6
    
    We trust you, Eric. (-:
    
    It's always good to work something out for yourself, isn't it?
    
    By the way, I think for this particular identity it is easier to
    multiply out rather than divide i.e.
    
    show that (p-1)(p^(n-1)+p^(n-2)+...+1) = p^n-1
    
    and hence arrive at the desired result ... but there are always
    different ways of getting there.
                                    
1911.9Number Theory ProblemDECWET::WOLFEThu Oct 12 1995 22:1115
I am  taking a number theory correspondance course and
have not been able the figure this out.  Any help,
suggestions would be appreciated.

Show that if n is composite, then there exists a prime 
p less than or equal to the square root of n such that 
p|n.

Hint : consider what happens when two numbers greater
than the square root of n are multiplied.

I can see this is true and have approached the problem
using the hint but am stuck.

Thanks for any help.
1911.10AUSSIE::GARSONachtentachtig kacheltjesFri Oct 13 1995 02:1912
    re .9
    
    Hint: Prove by reductio ad absurdum i.e. assume that n is composite
    but that for all prime p such that p|n, p > sqrt(n). This will lead to
    a contradiction from which you can conclude that for at least one prime
    p such that p|n, p <= sqrt(n).
    
    I don't think I can give more guidance without just exhibiting a proof.
    
    (P.S. Re your choice of topic. "Open" here means that *noone* has
    solved it.)
                                                                           
1911.11Got it.DECWET::WOLFEFri Oct 13 1995 05:172
    Thanks - I think I got it (assuming you dont use the hint).  Moderator
    please move this as appropriate.