if phi(n) + sigma(n) = n tau(n) then n is prime
Chris Venables
can anyone help with a proof of this result:
n is a positive integer
phi(n) denotes the number of positive integers not exceeding n that are
relatively prime to n
sigma(n) denotes the sum of the divisors of n
tau(n) denotes the number of positive divisors of n
prove that if
phi(n) + sigma(n) = n tau(n)
then n is prime
Julian Gilbey
More is true: it is an if and only if.
We deal with the case n=1 separately: phi(1)+sigma(1)=1+1=2,
2tau(1)=2.1=2 \not= 1, so the result holds for the non-prime 1.
For n>1, we rewrite the equation as n tau(n) - sigma(n) = phi(n),
that is
\sum_{d|n} n - \sum_{d|n} d = \sum_{(d,n)=1} 1
or
\sum_{d|n} (n - d) = \sum_{(d,n)=1} 1
where the sums are taken over appropriate values of d in the
range 1 <= d <= n.
Now 1|n and n|n, so the LHS is >= (n-1)+(n-n) = n-1.
Also, (1,n)=1, so the RHS is <= n-1.
If n is composite, there is some d in the range 1<d<n with d|n,
so the LHS > n-1, and equality cannot hold.
If n is prime, then the only divisors of n are 1 and n, so the
LHS - n-1, and every 1 <= d < n is coprime to n, so the RHS = n-1
as well. Thus equality holds.
Julian
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Julian Gilbey Email: J.D.G...@qmw.ac.uk
Dept of Mathematical Sciences
Queen Mary & Westfield College Finger me or talk to me at:
Mile End Road j...@goedel.maths.qmw.ac.uk
London E1 4NS, ENGLAND ( Logon info attached )
Christia...@skynet.be
In article <6n54db$5...@news5-gui.server.cableol.net>,
"Chris Venables" <chris.v...@diamond.co.uk> wrote:
>
> can anyone help with a proof of this result:
>
> n is a positive integer
>
> phi(n) denotes the number of positive integers not exceeding n that are
> relatively prime to n
>
> sigma(n) denotes the sum of the divisors of n
>
> tau(n) denotes the number of positive divisors of n
>
> prove that if
> phi(n) + sigma(n) = n tau(n)
> then n is prime
>
>
Let us write n = p_1^e_1 * .......... * p_m^e^m
the canonical factorization of n .
Then
phi(n) = m * (1-1/p_1) * ......(1-1/p_m) (Euler)
sigma(n) = ((p_1^(e_1+1))/(p_1-1)) * ....... * ((p_m^(e_m+1))/(p_m-1))
tau(n) = (e_1+1) * ..... * (e_m+1)
The only possible case for
phi(n) + sigma(n) = n * tau(n)
is one, and only one e_i = 1
and e_j = 0 when i is not j,
i.e. : n is a prime.
(In this case : phi(n) = n - 1, sigma(n) = (nｲ-1)/(n-1) = n+1, tau(n) = 2)
With best regards !
e-mail : Christia...@skynet.be
URL : http://users.skynet.be/radoux
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
S Thomeier
On Sun, 28 Jun 1998, Chris Venables wrote:
> can anyone help with a proof of this result:
>
> n is a positive integer
>
> phi(n) denotes the number of positive integers not exceeding n that are
> relatively prime to n
>
> sigma(n) denotes the sum of the divisors of n
>
> tau(n) denotes the number of positive divisors of n
>
> prove that if
> phi(n) + sigma(n) = n tau(n)
> then n is prime
>
>
Proof: Using the multiplicativity of the functions phi(n),
sigma(n) and tau(n) and the resulting explicit formulae in
terms of the prime decomposition of n (see any elementary
number theory textbook), an easy argument shows that for n>1
the RHS of phi(n) + sigma(n) = n * tau(n) must always be
strictly greater than the LHS, if n is NOT a prime.
In fact, this nice equality holds if and only if n is a prime,
because in that case both LHS and RHS are equal to 2n.
(Unfortunately, this necessary and sufficient condition is not
very useful in determining the primality of n.) :)
Hopefully this is of help.
S. Thomeier
Memorial University
St. John's, NF
Canada
Le Van Tri
Hi Chris,
Can you prove that the left hand side never get larger than the right
hand side. That is phi(n)+sigma(n)<=ntau(n) for all n. The equality
is obtained on primes n only.
Hints: these functions are multiplicative. I guess you will be able to
do it now :) either by induction or explicit formula of these functions.
Best,
Tri.
Chris Venables wrote in message <6n54db$5...@news5-gui.server.cableol.net>...
ilias kastanas 08-14-90
In article <6n54db$5...@news5-gui.server.cableol.net>,
Chris Venables <chris.v...@diamond.co.uk> wrote:
@
@n is a positive integer
@
@phi(n) denotes the number of positive integers not exceeding n that are
@relatively prime to n
@
@sigma(n) denotes the sum of the divisors of n
@
@tau(n) denotes the number of positive divisors of n
@
@prove that if
@phi(n) + sigma(n) = n tau(n)
@then n is prime
Hint: If n is not prime, n tau(n) - sigma(n) > n-1.
Ilias
Alain Verberkmoes
"Chris Venables" <chris.v...@diamond.co.uk> wrote:
> can anyone help with a proof of this result:
>
> n is a positive integer
>
> phi(n) denotes the number of positive integers not exceeding n that are
> relatively prime to n
>
> sigma(n) denotes the sum of the divisors of n
>
> tau(n) denotes the number of positive divisors of n
>
> prove that if
> phi(n) + sigma(n) = n tau(n)
> then n is prime
If n>1 then
phi(n) + sigma(n) <= n tau(n)
with equality iff n is prime.
Proof by induction on n. If n is prime equality holds. If n is a
higher power of a prime strict inequality holds. Otherwise write
n = a b with 1 < a, b < n and a, b coprime. Since phi, sigma, and
tau are multiplicative functions, we have
phi(n) + sigma(n) =
phi(a b) + sigma(a b) =
phi(a) phi(b) + sigma(a) sigma(b) <
[phi(a) + sigma(a)] [phi(b) + sigma(b)] <=
a tau(a) b tau(b) =
n tau(n).
Alain.