Advanced High-School Mathematics

SECTION 2.1 Elementary Number Theory 63

b

a

=q 1 +

1

q 2 +

1

q 3 +

1

... ...

qm− 1 +

1

qm

.

15. For any positive integern, letUnbe the set of all integers relatively
    prime ton. Now letm, nbe relatively prime positive integers and
    show that
    Umn=Um∩Un.


16. Letn >1 be an integer and define the so-calledEulerφ-function
    (or Euler’stotientfunction) by setting
    φ(n) = # of integersm, 1 ≤m < nwhich are relatively prime withn.

Now prove the following.

(a) Ifpis prime, thenφ(p) =p−1.

(b) Ifpis prime, and ifeis a positive integer, thenφ(pe) =

pe−^1 (p−1).

(c) If m andn are relatively prime, φ(mn) = φ(m)φ(n). (Hint:

Try this line of reasoning. Let 1≤k < mnand letrm, rnbe

the remainders ofkby dividing bymandn, respectively. Show

that if gcd(k,mn) = 1, then gcd(rm,m) = gcd(rn,n) = 1.

Conversely, assume that we have integers 1 ≤ rm < m and

1 ≤ rn < n with gcd(rm,m) = gcd(rn,n) = 1. Apply the

Euclidean trick to obtain integerss,sm,sn,t,tn,tmsatisfying

sm+tn= 1, smrm+tmm= 1, snrn+tnn= 1.

Letk=smrn+tnrm, and letkmnbe the remainder obtained

by dividingk by mn. Show that 1 ≤ kmn < mn and that

gcdkmn,mn) = 1. This sets up a correspondence between the

positive integers less thanmnand relatively prime tomnand

the pairs of integers less thanmandnand relatively prime to

mandn, respectively.)