# Uva 10179 – Irreducable Basic Fractions

## Definition

Euler function $Phi (n)$ (sometimes denoted $Varphi (n)$or ${ It phi} (n)$) – is the amount of numbers from $1$up to $n$prime to $n$. In other words, the number of properties in the interval $[1; n]$, the greatest common divisor of which a $n$root of unity.
The first few values ​​of this function ( A000010 in OEIS encyclopedia ):
$Phi (1) = 1,$
$Phi (2) = 1,$
$Phi (3) = 2$
$Phi (4) = 2$
$Phi (5) = 4.$

## Properties

The following three simple properties of the Euler – enough to learn how to calculate it for any number:
• If $p$– prime, then $Phi (p) = p-1$.
(This is obvious, since any number, except for the $p$relatively easy with him.)
• If $p$– simple $a$– positive integer, then $Phi (p ^ a) = p ^ ap ^ {a-1}$.
(Because the number of $p ^ a$not only relatively prime numbers of the form , which the pieces.)$pk$ $(K in mathcal {N})$$p ^ a / p = p ^ {a-1}$
• If $a$and $b$are relatively prime, then $Phi (ab) = phi (a) phi (b)$(“multiplicative” Euler function).
(This follows from the Chinese Remainder Theorem . Consider an arbitrary number $z le ab$. denote $x$and $y$the remainders $z$at $a$and $b$, respectively. then $z$prime to $ab$if and only if the $z$prime to $a$and $b$separately, or what is the same thing as $x$a one- simply $a$and $y$relatively prime to $b$. Applying the Chinese remainder theorem, we see that any pair of numbers $x$and the number of one-to-one correspondence , and this completes the proof.)$y$ $(X le a, ~ y le b)$$z$ $(Z le ab)$
From here you can get the Euler function for each $It n$through its factorization (decomposition $n$into prime factors)
if
$n = p_1 ^ {a_1} cdot p_2 ^ {a_2} cdot ldots cdot [...]$
(Where all $p_i$– simple), then
$Phi (n) = phi (p_1 ^ {a_1}) cdot phi (p_2 ^ {a_2}) [...]$
$= (P_1 ^ {a_1} - p_1 ^ {a_1-1}) cdot (p_2 ^ {a_2} - p_ [...]$
$= N cdot left (1 - {1 over p_1} right) cdot le [...]$

## Implementation

The simplest code that computes the Euler function, factoring the number of elementary method for $O ( sqrt n)$:
The key place for the calculation of the Euler function – is to find a factorization of the number $n$. This is achieved in a time much smaller $O ( sqrt {n})$

## Applications of the Euler function

The most famous and important property of the Euler expressed in Euler’s theorem :
$a ^ { phi (m)} equiv 1 pmod m,$

where $It a$and $It m$are relatively prime.

In the particular case where the $It m$simple Euler’s theorem turns into the so-called Fermat’s little theorem :
$a ^ {m-1} equiv 1 pmod m$

### Posted by Shipu Ahamed

This site uses Akismet to reduce spam. Learn how your comment data is processed.