euler function

**jimmyjimmyjimmy** · December 12th, 2009, 03:15 PM

Hi,

if phi(x) is the euler or totient function, find an x that satisfies

phi(x) = 13,000,000.

I started by seeing that 13000000 = (13)(5^6)(2^6)

And I know that phi(x) is multiplicative for relatively prime numbers.

And phi(2^7) = 2^6.

I just can't figure out how to do the rest, that is the 13 and 5^6 parts, if this is even a good way to think about the problem. Any hints would be appreciated. Thanks

**chisigma** · December 14th, 2009, 01:45 AM

A basic property of the Euler's phi function is that if $n_{1},n_{2},\dots, n_{k}$ are coprime, then...

$\varphi (n_{1}\cdot n_{2}\dots n_{k})= \varphi(n_{1})\cdot \varphi(n_{2})\dots \varphi (n_{k})$ (1)

Because is $13,000,000 = 13\cdot 5^{6}\cdot 2^{6}$ , we can search a set of prime numbers [why not?

...] $p_{1},p_{2},\dots, p_{k}$ so that...

$\varphi(p_{1})\cdot \varphi(p_{2})\dots \varphi (p_{k}) = 13,000,000$ (2)

Taking into account that for $p$ prime is...

$\varphi(p)= p-1$ (3)

... we verify that...

a) $5= 2^{2}+1$ is prime $\rightarrow \varphi(5)= 2^{2}$

b) $53= 13\cdot 2^{2}+1$ is prime $\rightarrow \varphi(53)= 13\cdot 2^{2}$

c) $62501= 5^{6}\cdot 2^{2}+1$ is prime $\rightarrow \varphi(62501)= 5^{6}\cdot 2^{2}$

From a) b) and c) and the properties (1) and (3) You find that solution [not neccesarly the only solution...] of equation (2) is...

$p= 5 \cdot 53 \cdot 62501 = 16,562,765$

Merry Christmas from Italy

$\chi$ $\sigma$

Math Help Forum: euler function

LinkBack

Thread Tools

Display

euler function

Similar Math Help Forum Discussions

Euler Function phi(n)

the Euler φ-function

euler phi-function

Euler's Phi Function

Euler's phi function