Prove for any given positive integer N there exist only finitely many integers n with φ(n) = N

Where φ denotes Euler's function. Conclude that φ(n) tends to infinity as n tends to infinity.

Now if n = (p1^a1)(p2^a2)(p3^a3)...(ps^as),
then φ(n) = φ(p1^a1)φ(p2^a2)φ(p3^a3)... φ(ps^as)
= (p1^a1-1)(p1-1)(p2^a2-1)(p2-1)(p3^a3-1)(… (ps^as-1)(ps-1) for primes p and integers a_i

Let N= positive integer, p= a prime greater than N say p=N+1 and let n=be an integer s.t phi(n)=N

If q>=p is a prime divisor of n which means this prime number will divide that integer exactly. Then n=(q^k)m for some k>=1 and q DOES NOT divide m.

Then Phi(n)=Phi(q^k)Phi(m)>= q-1>=p-1>N A CONTRADICTION!! No bueno therefore you can conclude no prime divisor of n will be greater than N+1

Now let n=(p_(a_1))^(a_1)...(p_(a_m))^(am) these are the distinct prime divisors of n for some 0
Phi(n)=Phi((p_(a_1))^(a_1))...Phi((p_(a… Re-write it as a multiplication of factors to make it pretty

now for each p_i; Phi(n)>=(p_i)^(a_(i-1))>N for the largest a_i.

You can conclude for each p_i there will be finitely many choices for the exponents of a_i. SO the set of these ns with phi(n)=N is a subset of a finite set...therefore it is finite..

lastly

for each positive integer N, there is a largest integer n with phi(n)=N... as n approaches infinity so does phi(n)

DONEE!!

no problem n gl w math 113

Report Abuse