Phi

Find the sum of all positive integers x x satisfying the following properties:

  • x x can be expressed as ( p q ) 2 (p \cdot q)^2 , where p p and q q are distinct prime numbers.

  • ϕ ( x ) = 840 \phi(x) = 840 .


Notation: ϕ ( ) \phi(\cdot) denotes the Euler's totient function .


The answer is 1225.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Áron Bán-Szabó
Jun 11, 2017

ϕ ( x ) = x ( 1 1 p ) ( 1 1 q ) = p 2 q 2 p 1 p q 1 q = p q ( p 1 ) ( q 1 ) \phi(x)=x(1-\frac{1}{p})(1-\frac{1}{q})=p^2q^2*\frac{p-1}{p}*\frac{q-1}{q}=pq(p-1)(q-1)

ϕ ( x ) = 840 = 2 3 3 5 7 \phi(x)=840=2^3*3*5*7 Suppose p < q p<q . So p p , p 1 p-1 , q 1 q-1 are smaller than q q . ϕ ( x ) \phi(x) 's biggest prime divisor is 7 7 , so q = 7 q=7 .

p ( p 1 ) = ϕ ( x ) q ( q 1 ) = 2 3 3 5 7 7 6 = 2 2 5 p(p-1)=\frac{\phi(x)}{q(q-1)}=\frac{2^3*3*5*7}{7*6}=2^2*5 .

In the left side the biggest prime divisor is p p , in the right side is 5 5 , so p = 5 p=5 . The only solution is:

x = p 2 q 2 = 5 2 7 2 = 25 49 = 1225 x=p^2q^2=5^2*7^2=25*49=\boxed{1225}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...