7
$\begingroup$

So I have a test in a couple of hours and I'm having trouble finding information on how to use the Euler totient function for a large number so I'm wondering if someone could give me step-by-step instructions? :)

Here's a sample question for the test:

Find $\psi(93296)$.

Could you also give instructions on finding the prime factorisation as well? I used an online calculator and it is $2^4 * 7^3 * 17$ but I wouldn't know how to calculate this.

$\endgroup$
  • 3
    $\begingroup$ If you want to prime factorize, simple start by dividing the number by prime $p$ until you can't and then move on to the next prime. For example, prime factorization of 27 is as follows. $27/2$, not possible. $27/3 = 9$. $9$ is still divisible by $3$ so continue and you get $3*3*3 = 27$ or in other words, the prime factors of $27$. This is, of course cumbersome with large numbers. $\endgroup$ – Jeel Shah Mar 1 '13 at 11:42
  • 6
    $\begingroup$ My advice is to chalk the test up as a learning experience, and next time, don't wait until two hours before the test to start learning the material. $\endgroup$ – Gerry Myerson Mar 1 '13 at 12:20
9
$\begingroup$

Euler's totient function gives all the numbers that are relatively prime to $n$, that are below $n$. This is Euler's formula:

$$\psi(n) = n \prod_{p|n} \left(1 -\frac{1}{p}\right) $$

In order to use the formula, we must first prime factorize $n$. Let's take a smaller number first. Suppose you want to use $\psi(n)$ for $36$ as stated in the wiki article. Then you would take the following steps.

  1. Prime factorize $n$
  2. Then apply "sub" (distinct) $p$ in and continue to do so until you have run out of distinct $p$'s

So, first for the prime factorization of $36$ or any number. Here's the process.

    Divide n by p
    if n mod p = 0 then continue to divide by n
    if not then move onto the next prime
    You are done when you are left with a prime number

For $36$ it would be the following process:

$36/2 = 18 \rightarrow $18 is still divisible by 2, so continue

$18/2 = 9 \rightarrow 9$ is odd and therefore not divisible by $2$. Move onto the next prime, $3$

$9/3 = 3 \rightarrow 3$ is a prime and you are complete.

Therefore, the prime factors of $36$ are: $2,2,3,3$ or in other words $2^2*3^2$. Once we have the prime factors of $n$ we can use the function.

$$\begin {align} &\psi(n) = n \prod_{p|n} \left(1- \frac{1}{p}\right)\\ &\psi(36) = 36 \prod_{p|n} \left(1- \frac{1}{2}\right)\left(1- \frac{1}{3}\right)\\ &=12 \end{align}$$

Therefore, there are $12$ below $36$ that are relatively prime to $36$.

For the example that you have provided it would look something like this:

$$\begin {align} &\psi(n) = n \prod_{p|n} \left(1- \frac{1}{p}\right)\\ &\psi(93296) = 93296 \prod_{p|n} \left(1- \frac{1}{2}\right)\left(1- \frac{1}{7}\right)\left(1- \frac{1}{17}\right)\\ &=37632 \end{align}$$

This is the basic process to use the Totient function, note that there are various other formulas that one can use, I find that this one is the easiest to understand. Furthermore, prime factorization should not be difficult if you know the primes below $100$.

P.S For practice, you can verify your answers here

$\endgroup$
  • 2
    $\begingroup$ That is really well explained! Thank you, you're a lifesaver :) $\endgroup$ – Fred Mar 1 '13 at 12:22
2
$\begingroup$

$ψ(93296)=ψ(2^4)\timesψ(7^3)\timesψ(17)$ =$(2^4-2^3)\times(7^3-7^2)\times(17-1)$ =$8\times294\times16$ =$37632$

$\endgroup$
  • 7
    $\begingroup$ Usually, giving some explanation of what you are doing helps immensely. Why do each of your equalities hold? Notice that that is the point! $\endgroup$ – Mariano Suárez-Álvarez Jun 26 '13 at 7:03
  • $\begingroup$ ya its correct. $\endgroup$ – Aria Jun 28 '13 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.