MHB Is g(n)=8n/15 Only When n Is Divisible by 3 and 5?

  • Thread starter Thread starter Poirot1
  • Start date Start date
  • Tags Tags
    Function Proof
AI Thread Summary
The discussion centers on proving that g(n) = 8n/15 if and only if n is divisible by 3 and 5, and by no other primes, using the Euler totient function. Participants suggest rewriting n as a product of powers of 3 and 5, leveraging the multiplicative property of the totient function. They emphasize that for g(n) to equal 8n/15, the product of the factors (1 - 1/p) must equal 8/15, which is only satisfied when n is composed solely of the primes 3 and 5. The proof involves demonstrating that any additional prime factors would alter the result. The conclusion confirms that the condition holds true exclusively for n being a product of 3 and 5.
Poirot1
Messages
243
Reaction score
0

Show that g(n)=8n/15 iff n is divisible by 3 and 5 and by no other primes, where g is the euler totient function.

How to go about the proof?




 
Mathematics news on Phys.org
Re: totient function proof

Rewrite $N$ as a product of powers of $3$ and $5$. Use the multiplicative property, and what is the totient of a prime power?

Full derivation below.

If $N = 3^m \cdot 5^n$ then $\varphi(N) = \varphi(3^m \cdot 5^n)$. Using the multiplicative property:

$$\varphi(3^m \cdot 5^n) = \varphi(3^m) \cdot \varphi(5^n)$$
And you know that for prime $p$ we have:

$$\varphi(p^k) = p^{k - 1} \cdot (p - 1)$$
And so:

$$\varphi(3^m) \cdot \varphi(5^n) = \left ( 3^{m - 1} \cdot (3 - 1) \right ) \cdot \left ( 5^{n - 1} \cdot (5 - 1) \right ) = 8 \cdot 3^{m - 1} \cdot 5^{n - 1}$$
And...

$$3^m \cdot 5^n = N ~ ~ ~ \implies ~ ~ ~ 3^m \cdot 5^n \cdot \left ( 3^{-1} \cdot 5^{-1} \right ) = 3^{m - 1} \cdot 5^{n - 1} = N \cdot 15^{-1}$$
And we conclude:

$$\varphi(N) = 8 \cdot 3^{m - 1} \cdot 5^{n - 1} = 8 \cdot N \cdot 15^{-1} = \frac{8}{15} \cdot N$$
 
Last edited:
Re: totient function proof

first n should be divisible by 3 and 5 since phi(n) is the number of the positive integers relatively prime with n
so phi(n) is integer for all n.
suppose n is divisible by another prime p, say
n = 3^r 5^s p^t...(1)
g is multiplicative
g(n) = g(3^r)\cdot g(5^s)\cdot g(p^t)

g(n) = 3^r \left( 1 - \frac{1}{3} \right) 5^s \left(1 - \frac{1}{5} \right)g(p^t)

g(n) = 3^r \left( \frac{2}{3} \right) 5^s \left(\frac{4}{5} \right) g(p^t)

g(n) =3^r\cdot 5^s \left( \frac{8}{15} \right) g(p^t)

from (1)
3^r\cdot 5^s = \frac{n}{p^t}

g(n) = \frac{8n}{15} \frac{g(p^t)}{p^t}
we want p such that g(p^t) = p^t , that's true for 1 just
 
Poirot said:

Show that g(n)=8n/15 iff n is divisible by 3 and 5 and by no other primes, where g is the euler totient function.

How to go about the proof?


The basic formula of the Euler's Totiens Function is...

$\displaystyle \varphi (n) = n\ \prod _{p|n} (1-\frac{1}{p})$ (1)

... so that Your equation...

$\displaystyle \varphi(n)= \frac{8\ n}{15}$ (2)

... is satisfied if...

$\displaystyle \prod _{p|n} (1-\frac{1}{p}) = \frac{8}{15}$ (3)

... and that happens only for $\displaystyle n= 3 \cdot 5 = 15$ ...

Kind regards

$\chi$ $\sigma$
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Back
Top