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

• MHB
• Poirot1
In summary, the proof shows that the Euler's Totient Function, g(n), is equal to 8n/15 if and only if n is divisible by both 3 and 5, and by no other primes. The proof uses the multiplicative property and the fact that phi(n) is an integer for all n. By rewriting n as a product of powers of 3 and 5, the equation is reduced to showing that the product of the values of the function for each prime factor is equal to 8/15. This only happens when n=15, showing that for any other prime factors, the equation will not hold true.
Poirot1

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?

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$

To prove that g(n)=8n/15 iff n is divisible by 3 and 5 and by no other primes, we can use the definition of the Euler totient function and the fundamental theorem of arithmetic.

First, let's define g(n) as the number of positive integers less than or equal to n that are relatively prime to n. This means that g(n) counts the number of integers that do not share any common factors with n, except for 1.

Next, let's consider the prime factorization of n. By the fundamental theorem of arithmetic, every positive integer can be uniquely expressed as a product of primes. So, we can write n as n = p1^a1 * p2^a2 * ... * pn^an, where p1, p2, ..., pn are distinct primes and a1, a2, ..., an are positive integers.

Now, let's look at the definition of g(n)=8n/15. We can rewrite this as g(n)=n * (8/15). This means that g(n) is equal to n multiplied by a fraction, where the numerator is 8 and the denominator is 15.

Using this information, we can deduce that for g(n) to equal 8n/15, n must be divisible by both 8 and 15. Since 8 and 15 are relatively prime, this means that n must be divisible by both 8 and 15, and therefore by their product, which is 120.

Furthermore, since n is divisible by 120, we can write n as n = 2^a * 3^b * 5^c, where a, b, and c are positive integers. This is because 120= 2^3 * 3^1 * 5^1, and any other prime factors of n would make it not relatively prime to 120.

Therefore, we have shown that n must be divisible by 3 and 5, and no other primes, in order for g(n) to equal 8n/15. This completes the proof.

1. What is the Totient function?

The Totient function, denoted as φ(n), also known as Euler's totient function, is a mathematical function that counts the number of positive integers less than or equal to n that are relatively prime to n.

2. How is the Totient function calculated?

The Totient function is calculated by finding all the positive integers less than or equal to n that are relatively prime to n. This can be done by finding the prime factorization of n and using the formula φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk), where p1, p2, ..., pk are the distinct prime factors of n.

3. What is the significance of the Totient function?

The Totient function has many applications in number theory, cryptography, and modular arithmetic. It is also used to solve various problems, such as finding the number of reduced fractions with a given denominator and determining the order of elements in a group.

4. What is the proof for the Totient function?

The proof for the Totient function is based on Euler's theorem, which states that if a and n are coprime positive integers, then a raised to the power of φ(n) is congruent to 1 modulo n. This proof can be extended to all positive integers using the Chinese remainder theorem.

5. What are some common misconceptions about the Totient function?

One common misconception is that the Totient function only works for prime numbers. However, it can be applied to any positive integer. Another misconception is that the Totient function is the same as the phi function, which is used in different branches of mathematics and has a slightly different definition.

Similar threads

• General Math
Replies
9
Views
10K
• General Math
Replies
5
Views
2K
• General Math
Replies
1
Views
1K
• General Math
Replies
6
Views
907
• General Math
Replies
6
Views
2K
• General Math
Replies
5
Views
2K
• General Math
Replies
5
Views
2K
• General Math
Replies
55
Views
4K
• Calculus and Beyond Homework Help
Replies
15
Views
3K
• Engineering and Comp Sci Homework Help
Replies
1
Views
194