MA 341 B1 - Spring 2005
Number Theory

Homework #8 -- Selected Solutions

Numerical exploration
  1. If p, q and r are prime numbers, find formulas for φ(p), φ(p2), φ(pq), and φ(pqr).
    Since every positive integer less than p (a prime) is relatively prime to p, we have that φ(p)=p-1.

    To compute φ(pq), we use the fact that

    φ(pq) = pq - (#'s divisible by p) - (#'s divisible by q) + (#'s divisible by pq).

    Note that the last term in the above expression needs to be there because when we take the numbers from 1 to pq and remove the ones that are divisible by p and the ones that are divisible by q, the ones that are divisible by pq are "removed twice". Of the numbers from 1 to pq, there are pq/p = q such numbers that are divisible by p. Likewise, there are pq/q = p such numbers that are divisible by q. The only number in this range that is divisible by both p and q is pq. Thus, φ(pq) = pq - p - q + 1 = (p-1)(q-1).

    To compute φ(pqr), we again count using "exclusion-inclusion". We have

    φ(pqr) = pqr - (#'s divisible by p) - (#'s divisible by q) - (#'s divisible by r) + (#'s divisible by pq) + (#' divisible by qr) + (#'s divisible by rs) - (#'s divisibile by pqr)
    = pqr - pq - qr - rs + p + q + r - 1 = (p-1)(q-1)(r-1)

  2. In Z7, we have 31=3, 32=2, 33=6, 34=4, 35=5, 36=1 and so we observe that the powers of 3 yield all non-zero elements mod 7 (i.e. the units).

    In Z9, we have 21=2, 22=4, 23=8, 24=7, 25=5, 26=1. Here we observe that all of the units are obtained by powers of 2. (Here we don't count the elements 0,3 and 6 since they are not relatively prime to the mod.)

    When powers of an element yield all of the units in a certain mod, we say that element is a generator -- so 2 is a generator in Z7 and 3 is a generator in Z7.

    Look at Zm for m = 2,3,...,19 and try to find a generator in each of these mods. (Some of the larger mods may try your patience -- nonetheless, be thorough in your computations.)

    Look carefully at your results and formulate a conjecture that describes exactly when Zm has a generator.

    mod a generator
    2 1
    3 2
    4 3
    5 2
    6 5
    7 3
    8 none
    9 2
    10 3
    11 2
    12 none
    13 2
    14 3
    15 none
    16 none
    17 3
    18 5
    19 2
  3. Find a solution to the linear Diophantine equation
    (1+2i)x + (3+2i)y = 1
    with x,y in Z[i].
    The euclidean algorithm yields:
    3+2i=(1+2i)*1+2
    1+2i=2*i+1
    2=1*2+0

    Using the "magic table" yields:
    1i2
    0111+i3+2i
    101i1+2i

    and we see that x=1+i and y=-i solves the given equation.

Prove or disprove and salvage if possible
(Make sure that you prove your salvage!)
  1. If a = b (mod m) and c = d (mod m) then ac = bd (mod m).
    By the definition of congruence, we have that a=b+km and c=d+rm for some integers r and k. Multiplying these equations yields ac=(b+km)(d+rm)=bd+dkm+brm+krm2. Therefore, we see that ac and bd differ by a multiple of m and thus, by defintion, ac=bd (mod m).
  2. If ac = bc (mod m) for some non-zero c then a = b (mod m).
    This is false. For instance, 5*3 = 1*3 (mod 6). To salvage the statement, we assume that gcd(c,m)=1.
    Proof 1: Since (c,m)=1, we know (from a theorem in class) that c is a unit mod m. Therefore, there exists some number r such that cr=1 (mod m). Then ac=bc (mod m) implies that acr=bcr (mod m) which implies a=b (mod m).
    Proof 2: Since ac=bc (mod m), we have that m | (a-b)c. By homework set #7, question 8, we then have that m | a - b (since gcd(c,m)=1). Lastly, by definition, a = b (mod m.)
  3. If α, β are in Z[i] such that α | β and β | α, then α = β.
    This is false. We can only deduce that α = uβ where u is a unit in Z[i].
    Proof: By the definition of divides, we have that there exists u and v in Z[i] such that αu = β and βv = α. Substituting then yields, αuv = α. If α=0, then β is also zero and our statement is true. Otherwise, if α is non-zero, then by cancellation in Z[i] (proven below), we have that uv=1. Therefore, by definition u and v are units proving our statement.
    Lemma: If αγ = βγ for γ non-zero, then α = β where α, β and γ are in Z[i].

    Proof: Every step in the proof of this fact in Z immediately generalizes except for the fact that the product of two non-zero Gaussian integers is again non-zero. We prove this below as a lemma.

    Lemma: If αβ = 0 then α = 0 or β=0 for α and β in Z[i].

    Proof I: Let α = a + bi and β = c + di. Then αβ = (a+bi)(c+di) = (ac-bd) + (ad+bc)i. Since this is assumed to be zero, we have ac=bd and ad=-bc. Multiplying the first equation by d yields acd=bd2 and substituting in the second equation yields -bc2=bd2. If b is non-zero, then cancellation in Z yeilds -c2 = d2. This is only possible is c=d=0. Thus, β=0.

    Thus, we may assume that b=0. The first equation then shows that either a=0 or c=0. If a=0, we are done since then α=0. If c=0, then by the second equation either a=0 or d=0. Again, if a=0 we are done and if d=0 then &beta=0 and we are done.

    Proof II: Taking norms yields N(αβ)=N(0)=0 and thus N(α)N(β)=0. Since we know this lemma already for Z and norms are integers, we can deduce that N(α)=0 or N(β)=0. But the norm of a Gaussian integer is zero if and only if that Gaussian integer is zero. Therefore, α=0 or β=0.