prove phi2(mn)=phi2(m)phi2(n) if m,n>1 and gcd(m,n)=1 (Quadratic Residues; Gener

Question

prove phi2(mn)=phi2(m)phi2(n) if m,n>1 and gcd(m,n)=1

(Quadratic Residues; General Modulus) Let m > 1 be an integer. Recall that a unit square x modulo m is a unit and a square modulo m; that is, x is invertible modulo m and there exists integer y such that x identical to y2 mod m. Let phi2(m) be the number of unit squares modulo m. Here two unit squares in the same congruence class are considered same. Prove that phi2(mn) = phi2(m) phi2(n) if m, n > 1 and (m, n) = 1. (Hint: follow the argument for phi(mm) = phi(m) phi(n) and apply Chinese Remainder Theorem)

Explanation / Answer

Let S1 = { x in Z/mnZ / x is an unit of Z/mnZ and x=y^2 [mn] for some y in Z/mnZ and gcd(x,mn)=1 }

By definition of phi_2 then |S1|=phi_2(mn)

Let S2 = { (y,z) in Z/mZ x Z/nZ /
y,z are units of Z/mZ and Z/nZ respectively
y=a^2[m] for some a in Z/mZ and gcd(y,m)=1
z=b^2[n] for some b in Z/nZ and gcd(z,n)=1
}

By definition of phi_2 then |S2|=phi_2(m)phi_2(n) since we have phi_2(m) ways to construct the first
coordinates and phi_2(n) to construct the second coordinate.


Let x in Z/mnZ in S1, let's take a look at the couple (x mod m, x mod n)

1

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.