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$
2
  • 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, 2013 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$ Mar 1, 2013 at 12:20

2 Answers 2

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$
1
  • 2
    $\begingroup$ That is really well explained! Thank you, you're a lifesaver :) $\endgroup$
    – Fred
    Mar 1, 2013 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$
2
  • 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$ Jun 26, 2013 at 7:03
  • $\begingroup$ ya its correct. $\endgroup$
    – Aria
    Jun 28, 2013 at 6:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .