Question

Exercise 2. Let φ denote the Euler totient function. (i) Prove that for all positive integers m and n, if m,n are relatively prime (coprime), then φ(mn-o(m)o(n) (ii) Is the converse true? Prove or provide a counter-example.

Answer 1

1.

first make numbers from 1 to mn in a rectangular table with m rows and n columns as below

1 m+1 2m+1 ...... (n-1)m+1

2 m+2 2m+2 ...... (n-1)m+2

3 m+3 2m+3 ...... (n-1)m+3

.

.

.

m 2m 3m ....... nm

here, the numbers in rth row are of the form km+r ( k changes from 0 to m-1 )

If two numbers are relative prime then gcd of those numbers is 1.

So if gcd(r,m) =1 , then every entry in rth row is realtive prime to m.

so gcd(km+r,m)=1 ( as mentioned above (m,n are coprime) )

We have shown that there are ϕ(m) rows in the table which contain numbers relatively prime to mn, and each of those contain exactly ϕ(n) such numbers.

So there are, in total, ϕ(m)ϕ(n) numbers in the table which are relatively prime to mn. This proves the theorem.

2. yes, the converse of Euler's Toient theorm is also true.

Suppose that for some B, a^B=1 mod n . Then we have some integers k,m and an equation of the form a^Bk+mn=1. This means that a^B and n are coprime. Then a and n must be coprime.