Ques 1: Solve 𝟑𝒙𝟐 + Proof of Wilson’s Theorem That means the entire product

Let 𝒑 be a prime number. collapses to the multiplication of

𝟓𝒙 + 𝟗 ≡ 𝟎 (𝐦𝐨𝐝 𝟏𝟏) We consider the set of all non- the two self-inverse elements,
Step 1: Compute the discriminant zero residue classes modulo 𝒑: since the rest of the factors cancel
modulo 11 {𝟏, 𝟐, 𝟑, … , 𝒑 − 𝟏}. out in inverse pairs.
The discriminant is These form a multiplicative group Thus,
𝚫 = 𝒃𝟐 − 𝟒𝒂𝒄 = 𝟓𝟐 − 𝟒(𝟑)(𝟗) under multiplication modulo 𝒑. (𝒑 − 𝟏)! ≡ 𝟏 ⋅ (𝒑 − 𝟏) (𝐦𝐨𝐝 𝒑).
= 𝟐𝟓 − 𝟏𝟎𝟖 Since 𝒑 is prime, every number 𝒂 Step 3: Simplify the result
= −𝟖𝟑. with 𝟏 ≤ 𝒂 ≤ 𝒑 − 𝟏 has a unique Now observe that
Reduce modulo 11: inverse modulo 𝒑. 𝒑 − 𝟏 ≡ −𝟏 (𝐦𝐨𝐝 𝒑).
−𝟖𝟑 ≡ −𝟖𝟑 + 𝟖𝟖 = 𝟓 (𝐦𝐨𝐝 𝟏𝟏). The idea is to look at the product Therefore,
So (𝒑 − 𝟏)! = 𝟏 ⋅ 𝟐 ⋅ 𝟑 ⋯ (𝒑 − 𝟏) (𝒑 − 𝟏)! ≡ −𝟏 (𝐦𝐨𝐝 𝒑).
𝚫 ≡ 𝟓 (𝐦𝐨𝐝 𝟏𝟏). and analyze how the inverses pair This completes the proof.
Step 2: Check if 5 has a square within this product. Final Conclusion
root modulo 11 Step 1: Identify the self-inverse For any prime number 𝒑, the
We check small squares mod 11 elements modulo 𝒑 factorial of 𝒑 − 𝟏 satisfies
and find A number 𝒂 is self-inverse if it (𝒑 − 𝟏)! ≡ −𝟏 (𝐦𝐨𝐝 𝒑) .
𝟒𝟐 ≡ 𝟏𝟔 ≡ 𝟓 (𝐦𝐨𝐝 𝟏𝟏). satisfies This is Wilson’s Theorem, and it
Thus 𝒂𝟐 ≡ 𝟏 (𝐦𝐨𝐝 𝒑). provides a necessary and
√𝟓 ≡ ±𝟒 (𝐦𝐨𝐝 𝟏𝟏). Rewrite it as sufficient condition for primality:
Step 3: Apply the modular 𝒂𝟐 − 𝟏 ≡ 𝟎 ⇒ (𝒂 − 𝟏)(𝒂 A number 𝒑 > 𝟏 is prime if and
quadratic formula + 𝟏) ≡ 𝟎 (𝐦𝐨𝐝 𝒑). only if
−𝒃 ± √𝚫 Because 𝒑 is prime, for a product (𝒑 − 𝟏)! ≡ −𝟏 (𝐦𝐨𝐝 𝒑).
𝒙≡ (𝐦𝐨𝐝 𝟏𝟏). to be congruent to zero modulo 𝒑,
𝟐𝒂 (Though theoretically important,
Here one of its factors must be divisible this is not practical for testing
−𝒃 ≡ −𝟓 ≡ 𝟔, 𝟐𝒂 = 𝟔. by 𝒑. Therefore, large primes.)
We need the inverse of 6 mod 11. 𝒂 ≡ 𝟏 (𝐦𝐨𝐝 𝒑) or 𝒂 ≡ −𝟏 Ques 3: Prove that 𝝋(𝒏)
𝟔 ⋅ 𝟐 = 𝟏𝟐 ≡ 𝟏 (𝐦𝐨𝐝 𝟏𝟏) ≡ 𝒑 − 𝟏 (𝐦𝐨𝐝 𝒑).
⇒ 𝟔 𝟏 ≡ 𝟐. So the only numbers in is a multiplicative
Thus {𝟏, 𝟐, … , 𝒑 − 𝟏} that satisfy function
𝒙 ≡ (𝟔 ± 𝟒) ⋅ 𝟐 (𝐦𝐨𝐝 𝟏𝟏). 𝒂 𝟏 ≡ 𝒂 (𝐦𝐨𝐝 𝒑) We want to prove that Euler’s
Case 1: 𝟔 + 𝟒 = 𝟏𝟎 are totient function 𝝋(𝒏) is
𝒙 ≡ 𝟏𝟎 ⋅ 𝟐 = 𝟐𝟎 ≡ 𝟗 (𝐦𝐨𝐝 𝟏𝟏). 𝟏 and 𝒑 − 𝟏. multiplicative, meaning:
Case 2: 𝟔 − 𝟒 = 𝟐 No other number in this range is If 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏, then
𝒙 ≡ 𝟐 ⋅ 𝟐 = 𝟒 (𝐦𝐨𝐝 𝟏𝟏). self-inverse. 𝝋(𝒎𝒏) = 𝝋(𝒎)𝝋(𝒏).
Final Answer Step 2: Pair all other numbers This is one of the fundamental
𝒙 ≡ 𝟒, 𝟗 (𝐦𝐨𝐝 𝟏𝟏). with their inverses properties of 𝝋(𝒏) in elementary
These are the complete solutions Now consider every number 𝒂 in number theory.
of the quadratic congruence. the range Step 1: Interpret 𝝋(𝒏) in terms of
Ques 2: State and prove 𝟐, 𝟑, … , 𝒑 − 𝟐. counting
Since each such 𝒂 has a unique The totient function 𝝋(𝒏) counts
Wilson’s Theorem inverse modulo 𝒑, and since none the number of integers between 𝟏
Statement of Wilson’s Theorem: of these numbers are self-inverse, and 𝒏 that are coprime to 𝒏.
For any prime number 𝒑, the inverse of 𝒂 is a different So,
(𝒑 − 𝟏)! ≡ −𝟏 (𝐦𝐨𝐝 𝒑). number, also in this range. 𝝋(𝒏) = |{ 𝟏 ≤ 𝒂 ≤ 𝒏: (𝒂, 𝒏)
Equivalently, Thus, each pair (𝒂, 𝒂 𝟏 ) satisfies = 𝟏 }|.
(𝒑 − 𝟏)! ≡ 𝒑 − 𝟏 (𝐦𝐨𝐝 𝒑).
𝒂 ⋅ 𝒂 𝟏 ≡ 𝟏 (𝐦𝐨𝐝 𝒑). Therefore, to prove
This theorem characterizes multiplicativity, we must show
Because the factorial (𝒑 − 𝟏)!
primes using factorials and is one that the number of integers
includes each number from 𝟏 to
of the fundamental results in
𝒑 − 𝟏, every such pair contributes between 𝟏 and 𝒎𝒏 that are
elementary number theory.
a factor of 𝟏 to the product coprime to 𝒎𝒏 equals the
modulo 𝒑. product of:
  the number of integers Ques 4: Prove that if We want to compute
between 𝟏 and 𝒎 coprime 𝟐𝟗𝟐𝟎𝟐𝟒 𝐦𝐨𝐝 𝟓𝟎𝟎.
to 𝒎, and
(𝒂, 𝒏) = 𝟏 then (𝒏 − Since 𝟓𝟎𝟎 = 𝟒 × 𝟏𝟐𝟓, we will use
 the number of integers 𝒂, 𝒏) = 𝟏 the Chinese Remainder Theorem
between 𝟏 and 𝒏 coprime We are asked to show that if an by finding:
to 𝒏. integer 𝒂 is coprime to 𝒏, then the 1. 𝟐𝟗𝟐𝟎𝟐𝟒 𝐦𝐨𝐝 𝟒
Step 2: Use the fact that integer 𝒏 − 𝒂 is also coprime to 𝒏. 2. 𝟐𝟗𝟐𝟎𝟐𝟒 𝐦𝐨𝐝 𝟏𝟐𝟓
𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏 In symbolic form: Then we combine the results.
Since 𝒎 and 𝒏 are coprime, the If Step 1: Compute 𝟐𝟗𝟐𝟎𝟐𝟒 𝐦𝐨𝐝 𝟒
integers modulo 𝒎𝒏 can be 𝐠𝐜𝐝(𝒂, 𝒏) = 𝟏, 𝟐𝟗 ≡ 𝟏 (𝐦𝐨𝐝 𝟒)
represented as ordered pairs then So,
modulo 𝒎 and modulo 𝒏. 𝐠𝐜𝐝(𝒏 − 𝒂, 𝒏) = 𝟏. 𝟐𝟗𝟐𝟎𝟐𝟒 ≡ 𝟏𝟐𝟎𝟐𝟒 ≡ 𝟏 (𝐦𝐨𝐝 𝟒).
This is a consequence of the Proof Step 2: Compute
Chinese Remainder Theorem Let 𝐠𝐜𝐝(𝒂, 𝒏) = 𝟏. 𝟐𝟗𝟐𝟎𝟐𝟒 𝐦𝐨𝐝 𝟏𝟐𝟓
(CRT): This means no prime number We use Euler’s theorem.
Each integer 𝒙 modulo 𝒎𝒏 divides both 𝒂 and 𝒏. 𝟏
corresponds uniquely to the pair We want to prove that the same 𝝓(𝟏𝟐𝟓) = 𝟏𝟐𝟓 𝟏 − = 𝟏𝟎𝟎.
𝟓
(𝒙 𝐦𝐨𝐝 𝒎, 𝒙 𝐦𝐨𝐝 𝒏). holds for 𝒏 − 𝒂 and 𝒏. Thus,
Thus, the system is equivalent Step 1: Let a common divisor of 𝟐𝟗𝟏𝟎𝟎 ≡ 𝟏 (𝐦𝐨𝐝 𝟏𝟐𝟓).
and preserves structure. 𝒏 − 𝒂 and 𝒏 be 𝒅 Now reduce exponent:
Step 3: Determine when an Suppose a positive integer 𝒅 𝟐𝟎𝟐𝟒 = 𝟏𝟎𝟎 ⋅ 𝟐𝟎 + 𝟐𝟒.
integer is coprime to 𝒎𝒏 divides both 𝒏 and 𝒏 − 𝒂. So,
An integer 𝒙 is coprime to 𝒎𝒏 if So, 𝟐𝟗𝟐𝟎𝟐𝟒 ≡ 𝟐𝟗𝟐𝟒 (𝐦𝐨𝐝 𝟏𝟐𝟓).
and only if it is coprime 𝒅 ∣ 𝒏, 𝒅 ∣ (𝒏 − 𝒂). We now compute powers
separately to both 𝒎 and 𝒏. That If 𝒅 divides both quantities, then gradually:
is: it must also divide their First compute 𝟐𝟗𝟐 :
(𝒙, 𝒎𝒏) = 𝟏 ⇔ (𝒙, 𝒎) difference. 𝟐𝟗𝟐 = 𝟖𝟒𝟏 ≡ 𝟖𝟒𝟏 − 𝟕𝟓𝟎
= 𝟏 and (𝒙, 𝒏) = 𝟏. Compute the difference: = 𝟗𝟏 (𝐦𝐨𝐝 𝟏𝟐𝟓).
This uses 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏. (𝒏) − (𝒏 − 𝒂) = 𝒂. 𝟒
Then 𝟐𝟗 :
Step 4: Count the number of Thus,
𝟐𝟗𝟒 ≡ 𝟗𝟏𝟐 = 𝟖𝟐𝟖𝟏.
allowed pairs 𝒅 ∣ 𝒂.
Reduce mod 125:
Using CRT: So we now have
𝟖𝟐𝟖𝟏 − 𝟖𝟎𝟎𝟎 = 𝟐𝟖𝟏, 𝟐𝟖𝟏
 The number of residues 𝒅 ∣ 𝒏 and 𝒅 ∣ 𝒂.
− 𝟐𝟓𝟎 = 𝟑𝟏.
modulo 𝒎 that are Step 2: Use the given condition
Thus,
coprime to 𝒎 is 𝝋(𝒎). 𝐠𝐜𝐝(𝒂, 𝒏) = 𝟏
𝟐𝟗𝟒 ≡ 𝟑𝟏 (𝐦𝐨𝐝 𝟏𝟐𝟓).
 The number of residues Since (𝒂, 𝒏) = 𝟏, the only
Then 𝟐𝟗𝟖 :
modulo 𝒏 that are coprime common divisor of 𝒂 and 𝒏 is 1.
But we just proved any common 𝟐𝟗𝟖 ≡ 𝟑𝟏𝟐 = 𝟗𝟔𝟏 ≡ 𝟗𝟔𝟏 − 𝟖𝟕𝟓
to 𝒏 is 𝝋(𝒏). = 𝟖𝟔 (𝐦𝐨𝐝 𝟏𝟐𝟓).
Since each allowed residue mod divisor of 𝒏 and 𝒏 − 𝒂 also 𝟏𝟔
divides both 𝒂 and 𝒏. Then 𝟐𝟗 :
𝒎 can pair with each allowed
Therefore, the only possibility is 𝟐𝟗𝟏𝟔 ≡ 𝟖𝟔𝟐 = 𝟕𝟑𝟗𝟔.
residue mod 𝒏, the total number
𝒅 = 𝟏. Reduce:
of allowed pairs is
So no integer greater than 1 can 𝟕𝟑𝟗𝟔 − 𝟕𝟐𝟓𝟎 = 𝟏𝟒𝟔, 𝟏𝟒𝟔
𝝋(𝒎) × 𝝋(𝒏).
divide both 𝒏 − 𝒂 and 𝒏. − 𝟏𝟐𝟓 = 𝟐𝟏.
And since each such pair
Thus,
corresponds to exactly one
Conclusion 𝟐𝟗𝟏𝟔 ≡ 𝟐𝟏 (𝐦𝐨𝐝 𝟏𝟐𝟓).
number modulo 𝒎𝒏, we have
Now,
𝝋(𝒎𝒏) = 𝝋(𝒎)𝝋(𝒏). 𝐠𝐜𝐝(𝒏 − 𝒂, 𝒏) = 𝟏 .
𝟐𝟗𝟐𝟒 = 𝟐𝟗𝟏𝟔 ⋅ 𝟐𝟗𝟖 ⋅ 𝟐𝟗𝟎 .
Conclusion Thus, if 𝒂 is coprime to 𝒏, then so So,
Thus, for any two coprime is 𝒏 − 𝒂.
positive integers 𝒎 and 𝒏, 𝟐𝟗𝟐𝟒 ≡ 𝟐𝟏 ⋅ 𝟖𝟔 (𝐦𝐨𝐝 𝟏𝟐𝟓).
Ques 5: Find the Compute:
𝝋(𝒎𝒏) = 𝝋(𝒎)𝝋(𝒏) .
This proves that Euler’s totient
remainder when 𝟐𝟗𝟐𝟎𝟐𝟒 𝟐𝟏 ⋅ 𝟖𝟔 = 𝟏𝟖𝟎𝟔.
Reduce mod 125:
function is multiplicative. is divided by 500
 𝟏𝟖𝟎𝟔 − 𝟏𝟕𝟓𝟎 = 𝟓𝟔. Step 2: Study powers of 3 modulo {𝒂, 𝟐𝒂, 𝟑𝒂, … , (𝒑 − 𝟏)𝒂}
Thus, 4 is simply a permutation of
𝟐𝟗𝟐𝟒 ≡ 𝟓𝟔 (𝐦𝐨𝐝 𝟏𝟐𝟓). Let us compute the first few {𝟏, 𝟐, 𝟑, … , 𝒑 − 𝟏}.
Therefore: powers of 3 modulo 4: Step 2: Multiply all elements
𝟐𝟗𝟐𝟎𝟐𝟒 ≡ 𝟓𝟔 (𝐦𝐨𝐝 𝟏𝟐𝟓) . 𝟑𝟏 = 𝟑 ≡ 𝟑 (𝐦𝐨𝐝 𝟒), Take the product of all numbers
𝟑𝟐 = 𝟗 ≡ 𝟏 (𝐦𝐨𝐝 𝟒). in the first set:
Step 3: Solve the system using
This is the key observation: 𝟏 ⋅ 𝟐 ⋅ … ⋅ (𝒑 − 𝟏).
CRT
𝟑𝟐 ≡ 𝟏 (𝐦𝐨𝐝 𝟒). In the second set:
We have:
Any higher even power of 3 will (𝒂 ⋅ 𝟏)(𝒂 ⋅ 𝟐) ⋯ (𝒂 ⋅ (𝒑 − 𝟏))
𝟐𝟗𝟐𝟎𝟐𝟒 ≡ 𝟏 (𝐦𝐨𝐝 𝟒),
be a power of 𝟑𝟐 , and therefore = 𝒂𝒑 𝟏 (𝟏 ⋅ 𝟐 ⋅ … ⋅ (𝒑
𝟐𝟗𝟐𝟎𝟐𝟒 ≡ 𝟓𝟔 (𝐦𝐨𝐝 𝟏𝟐𝟓).
will also be congruent to 1 − 𝟏)).
We want a number 𝒙 such that:
modulo 4. Since the two sets are
𝒙 ≡ 𝟓𝟔 (𝐦𝐨𝐝 𝟏𝟐𝟓), permutations of each other
𝒙 ≡ 𝟏 (𝐦𝐨𝐝 𝟒). Step 3: Express 𝟑𝟏𝟎𝟎 using 𝟑𝟐
Since: modulo 𝒑, their products are
Write 𝒙 = 𝟓𝟔 + 𝟏𝟐𝟓𝒌. congruent:
Now impose the condition 𝟑𝟏𝟎𝟎 = (𝟑𝟐 )𝟓𝟎 ,
we substitute the modular value: 𝒂𝒑 𝟏 (𝒑 − 𝟏)! ≡ (𝒑
𝟓𝟔 + 𝟏𝟐𝟓𝒌 ≡ 𝟏 (𝐦𝐨𝐝 𝟒).
(𝟑𝟐 )𝟓𝟎 ≡ 𝟏𝟓𝟎 (𝐦𝐨𝐝 𝟒). − 𝟏)! (𝐦𝐨𝐝 𝒑).
Reduce modulo 4:
And of course, Step 3: Cancel (𝒑 − 𝟏)! modulo 𝒑
 𝟓𝟔 ≡ 𝟎
𝟏𝟓𝟎 = 𝟏. We know from Wilson’s Theorem
 𝟏𝟐𝟓 ≡ 𝟏 that:
So the condition becomes: Thus,
𝟑𝟏𝟎𝟎 ≡ 𝟏 (𝐦𝐨𝐝 𝟒). (𝒑 − 𝟏)! ≢ 𝟎 (𝐦𝐨𝐝 𝒑).
𝒌 ≡ 𝟏 (𝐦𝐨𝐝 𝟒). Since 𝒑 is prime, every non-zero
Thus, Ques 7: Let 𝒑 be a prime residue has a multiplicative
𝒌 = 𝟏 + 𝟒𝒕. and suppose 𝒑 ∤ 𝒂. Prove inverse modulo 𝒑.
Now plug back: Thus we may divide both sides of
𝒙 = 𝟓𝟔 + 𝟏𝟐𝟓(𝟏 + 𝟒𝒕). that
𝒂𝒑 𝟏 (𝒑 − 𝟏)! ≡ (𝒑
𝒙 = 𝟓𝟔 + 𝟏𝟐𝟓 + 𝟓𝟎𝟎𝒕. 𝒂 𝒑 𝟏 ≡ 𝟏 (𝐦𝐨𝐝 𝒑). − 𝟏)! (𝐦𝐨𝐝 𝒑)
𝒙 = 𝟏𝟖𝟏 + 𝟓𝟎𝟎𝒕. (This is Fermat’s Little by (𝒑 − 𝟏)!, yielding:
Thus the number modulo 500 is: Theorem.)** 𝒂𝒑 𝟏 ≡ 𝟏 (𝐦𝐨𝐝 𝒑).
𝟏𝟖𝟏 . We are asked to prove a classical Final Conclusion
Ques 6: Find the and fundamental theorem in
number theory: Fermat’s Little 𝒂 𝒑 𝟏 ≡ 𝟏 (𝐦𝐨𝐝 𝒑)
remainder when 𝟐𝟑𝟏𝟎𝟎 is Theorem. whenever 𝒑 is prime and 𝒑 ∤ 𝒂.
divided by 4 The condition “𝒑 + 𝒂” in the This completes the proof of
We are asked to compute the question simply means 𝒂 is not a Fermat’s Little Theorem.
value of multiple of 𝒑; that is, Ques 8: Prove that the
𝟐𝟑𝟏𝟎𝟎 𝐦𝐨𝐝 𝟒. 𝐠𝐜𝐝(𝒂, 𝒑) = 𝟏.
Möbius function 𝝁(𝒏) is
Since the exponent is extremely Step 1: Consider the set of non-
large, we cannot compute it zero residues modulo 𝒑 multiplicative
directly. Since 𝒑 is prime, the set The Möbius function 𝝁(𝒏) is
Instead, we simplify the base {𝟏, 𝟐, 𝟑, … , 𝒑 − 𝟏} defined as:
modulo 4 and use the behavior of forms a multiplicative group 𝝁(𝒏)
powers under modular modulo 𝒑. 𝟏, if 𝒏 = 𝟏,
arithmetic. Every element in this set has a = (−𝟏)𝒌 , if 𝒏 is of 𝒌 distinct prim
Step 1: Reduce 23 modulo 4 multiplicative inverse modulo 𝒑. 𝟎, if 𝒏 is divisible by a squ
We begin by reducing the base: Now multiply every element in We want to prove that 𝝁(𝒏) is
𝟐𝟑 ÷ 𝟒 = 𝟓 remainder 𝟑. this set by 𝒂. multiplicative, meaning:
Thus, The new set is: If 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏, then
𝟐𝟑 ≡ 𝟑 (𝐦𝐨𝐝 𝟒). 𝒂 ⋅ 𝟏, 𝒂 ⋅ 𝟐, 𝒂 ⋅ 𝟑, … , 𝒂 ⋅ (𝒑 − 𝟏). 𝝁(𝒎𝒏) = 𝝁(𝒎)𝝁(𝒏).
This allows us to replace the Because 𝒂 is coprime to 𝒑, Step 1: Use the definition of
original expression with: multiplication by 𝒂 does not multiplicative functions
𝟐𝟑𝟏𝟎𝟎 ≡ 𝟑𝟏𝟎𝟎 (𝐦𝐨𝐝 𝟒). create duplicates modulo 𝒑. A function 𝒇(𝒏) is multiplicative
Thus the set if it satisfies:
 1. 𝒇(𝟏) = 𝟏,  𝒎𝒏 contains 𝒓 + 𝒔 distinct Every divisor of 𝒎𝒏 can be
2. 𝒇(𝒎𝒏) = 𝒇(𝒎)𝒇(𝒏) primes because no primes written uniquely as a product
whenever 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏. overlap. 𝒅𝟏 𝒅𝟐 , where 𝒅𝟏 ∣ 𝒎 and 𝒅𝟐 ∣ 𝒏.
The Möbius function clearly Thus: This is because the prime
satisfies 𝝁(𝟏) = 𝟏. 𝝁(𝒎) = (−𝟏)𝒓 , 𝝁(𝒏) factorizations of 𝒎 and 𝒏 do not
Now we must prove the second = (−𝟏)𝒔 , share any primes.
property. 𝝁(𝒎𝒏) = (−𝟏)𝒓 𝒔 . So, the set of divisors of 𝒎𝒏 is
Step 2: Consider three cases Now compute: exactly:
based on the definition of 𝝁(𝒏) 𝝁(𝒎)𝝁(𝒏) = (−𝟏)𝒓 (−𝟏)𝒔 { 𝒅𝟏 𝒅𝟐 : 𝒅𝟏 ∣ 𝒎, 𝒅𝟐 ∣ 𝒏 }.
To evaluate 𝝁(𝒎𝒏), we must = (−𝟏)𝒓 𝒔 . Step 2: Write 𝝈(𝒎𝒏) in terms of
examine whether: So: divisors of 𝒎 and 𝒏
1. 𝒎𝒏 contains a squared 𝝁(𝒎𝒏) = 𝝁(𝒎)𝝁(𝒏). Using the fact above:
prime factor, This shows multiplicativity holds
𝝈(𝒎𝒏) = 𝒅
2. 𝒎𝒏 is square-free but has for square-free numbers.
𝒅 ∣ 𝒎𝒏
𝒌 distinct primes, Case 3: One is square-free and the
3. or the combination of other contains a square = ( 𝒅𝟏 𝒅𝟐 ).
primes in 𝒎 and 𝒏 Similar to Case 1: 𝒅𝟏 ∣𝒎 𝒅𝟐 ∣𝒏
interacts in a way that If 𝒎 contains a square, 𝝁(𝒎) = Because every divisor 𝒅 of 𝒎𝒏 is
preserves the square-free 𝟎. of the form 𝒅𝟏 𝒅𝟐 :
property. Since primes in 𝒎 do not appear 𝝈(𝒎𝒏) = ( 𝒅𝟏 𝒅𝟐 )
Since 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏, no prime in 𝒏, this square factor remains in 𝒅𝟏 ∣𝒎 𝒅𝟐 ∣𝒏
divides both 𝒎 and 𝒏. the product:
Thus their prime factorization 𝒑𝟐 ∣ 𝒎 ⇒ 𝒑𝟐 ∣ 𝒎𝒏, = 𝒅𝟏 𝒅𝟐 .
structures do not overlap. so: 𝒅𝟏 ∣𝒎 𝒅𝟐 ∣𝒏
Let: 𝝁(𝒎𝒏) = 𝟎 = 𝝁(𝒎)𝝁(𝒏).
But:
𝒎 = 𝒑 𝟏 𝒑𝟐 ⋯ 𝒑 𝒓 , 𝒏 Again, multiplicativity holds.
= 𝒒𝟏 𝒒𝟐 ⋯ 𝒒𝒔 , Final Conclusion 𝒅𝟏 = 𝝈(𝒎), 𝒅𝟐
where all 𝒑𝒊 , 𝒒𝒋 are distinct For all coprime positive integers 𝒅𝟏 ∣𝒎 𝒅𝟐 ∣𝒏
primes. 𝒎, 𝒏: = 𝝈(𝒏).
Because 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏, none of 𝝁(𝒎𝒏) = 𝝁(𝒎)𝝁(𝒏) . So we get:
the primes repeat across 𝒎 and 𝝈(𝒎𝒏) = 𝝈(𝒎)𝝈(𝒏).
Thus the Möbius function 𝝁(𝒏) is
𝒏. This is exactly the multiplicativity
multiplicative.
Case 1: Either 𝒎 or 𝒏 contains a property.
This completes the proof.
squared prime Step 3: Why this works only when
Ques 9: Prove that the 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏
Suppose 𝒑𝟐 ∣ 𝒎.
Then 𝝁(𝒎) = 𝟎. Arithmetic Function If 𝒎 and 𝒏 are not coprime, their
Since 𝒑 does not divide 𝒏, the 𝝈(𝒏) is multiplicative prime factorizations overlap, and
same square divides 𝒎𝒏: a divisor of 𝒎𝒏 cannot be written
The arithmetic function 𝝈(𝒏) is
𝒑𝟐 ∣ 𝒎𝒏 ⇒ 𝝁(𝒎𝒏) = 𝟎. uniquely as 𝒅𝟏 𝒅𝟐 with 𝒅𝟏 ∣ 𝒎 and
defined as:
Thus, 𝒅𝟐 ∣ 𝒏.
𝝈(𝒏) = 𝒅, Therefore the double-sum
𝝁(𝒎𝒏) = 𝟎 = 𝝁(𝒎)𝝁(𝒏).
Similarly if 𝒏 contains a square
𝒅∣𝒏 expression would fail.
i.e., the sum of all positive divisors So the condition 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏 is
factor. of 𝒏.
Hence multiplicativity holds in essential.
We want to prove that 𝝈(𝒏) is Final Conclusion
this case.
multiplicative, meaning: 𝝈(𝒏) is multiplicative.
Case 2: Both 𝒎 and 𝒏 are square-
If 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏, then
free For all positive integers 𝒎, 𝒏 such
𝝈(𝒎𝒏) = 𝝈(𝒎)𝝈(𝒏) .
Then: that 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏:
 𝒎 contains 𝒓 distinct Step 1: Understand the divisors of 𝝈(𝒎𝒏) = 𝝈(𝒎)𝝈(𝒏) .
primes, a coprime product
This completes the proof.
 𝒏 contains 𝒔 distinct Let 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏.
A fundamental fact from number Ques 10: Find the remainder
primes,
theory is: when 𝟕𝟐𝟏𝟎𝟎𝟏 is divided by 31
We want to compute 𝟏𝟒 ⋅ 𝟕 = 𝟗𝟖 ≡ 𝟗𝟖 − 𝟗𝟑 Part 2: Prove that 𝝈(𝒏) is
𝟕𝟐𝟏𝟎𝟎𝟏 𝐦𝐨𝐝 𝟑𝟏. = 𝟓 (𝐦𝐨𝐝 𝟑𝟏). multiplicative
Because the exponent is extremely Then: Step 1: Use same unique
large, we use modular reduction 𝟓 ⋅ 𝟏𝟎 = 𝟓𝟎 ≡ 𝟓𝟎 − 𝟑𝟏 representation of divisors
and Fermat’s Little Theorem. = 𝟏𝟗 (𝐦𝐨𝐝 𝟑𝟏). Again, every divisor of 𝒎𝒏 is of
Step 1: Reduce the base modulo Thus, the form 𝒅𝟏 𝒅𝟐 , with
31 𝟏𝟎𝟏𝟏 ≡ 𝟏𝟗 (𝐦𝐨𝐝 𝟑𝟏). 𝒅𝟏 ∣ 𝒎 and 𝒅𝟐 ∣ 𝒏.
𝟕𝟐 ≡ 𝟕𝟐 − 𝟔𝟐 = 𝟏𝟎 (𝐦𝐨𝐝 𝟑𝟏) Final Answer Step 2: Sum the divisors
since 𝟔𝟐 = 𝟐 × 𝟑𝟏. 𝟏𝟗 𝝈(𝒎𝒏) = 𝒅
Thus, The remainder when 𝟕𝟐𝟏𝟎𝟎𝟏 is 𝒅∣𝒎𝒏
𝟕𝟐𝟏𝟎𝟎𝟏 ≡ 𝟏𝟎𝟏𝟎𝟎𝟏 (𝐦𝐨𝐝 𝟑𝟏). divided by 31 is 19.
Step 2: Apply Fermat’s Little = ( 𝒅𝟏 𝒅𝟐 ).
Ques 11: Prove that the 𝒅𝟏 ∣𝒎 𝒅𝟐 ∣𝒏
Theorem
Since 31 is prime: arithmetic functions 𝝉(𝒏) Factor the double sum:
𝒂𝟑𝟎 ≡ 𝟏 (𝐦𝐨𝐝 𝟑𝟏) if 𝐠𝐜𝐝(𝒂, 𝟑𝟏) and 𝝈(𝒏) are both
𝝈(𝒎𝒏) = 𝒅𝟏 𝒅𝟐 .
= 𝟏. multiplicative 𝒅𝟏 ∣𝒎 𝒅𝟐 ∣𝒏
Here 𝟏𝟎 and 𝟑𝟏 are coprime, so: Here,
𝟏𝟎𝟑𝟎 ≡ 𝟏 (𝐦𝐨𝐝 𝟑𝟏). But the sums are:
 𝝉(𝒏) = number of positive
Now reduce exponent 1001 divisors of 𝒏 𝒅𝟏 = 𝝈(𝒎), 𝒅𝟐
modulo 30:  𝝈(𝒏) = sum of positive 𝒅𝟏 ∣𝒎 𝒅𝟐 ∣𝒏
𝟏𝟎𝟎𝟏 = 𝟑𝟎 ⋅ 𝟑𝟑 + 𝟏𝟏. divisors of 𝒏 = 𝝈(𝒏).
So, We must prove that both are Thus,
𝟏𝟎𝟏𝟎𝟎𝟏 = (𝟏𝟎𝟑𝟎 )𝟑𝟑 ⋅ 𝟏𝟎𝟏𝟏 multiplicative functions, meaning 𝝈(𝒎𝒏) = 𝝈(𝒎)𝝈(𝒏).
≡ 𝟏𝟑𝟑 ⋅ 𝟏𝟎𝟏𝟏 that if So 𝝈(𝒏) is multiplicative.
≡ 𝟏𝟎𝟏𝟏 (𝐦𝐨𝐝 𝟑𝟏). 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏, Final Conclusion
Thus the problem reduces to then Both functions satisfy
calculating: 𝝉(𝒎𝒏) = 𝝉(𝒎)𝝉(𝒏), 𝝈(𝒎𝒏) multiplicativity:
𝟏𝟎𝟏𝟏 𝐦𝐨𝐝 𝟑𝟏. = 𝝈(𝒎)𝝈(𝒏). 𝝉(𝒎𝒏) = 𝝉(𝒎)𝝉(𝒏)
Step 3: Compute powers of 10 Part 1: Prove that 𝝉(𝒏) is 𝝈(𝒎𝒏) = 𝝈(𝒎)𝝈(𝒏) .
modulo 31 multiplicative Therefore, both arithmetic
We compute step by step: Step 1: Use coprimeness to
functions 𝝉(𝒏) and 𝝈(𝒏) are
Compute 𝟏𝟎𝟐 : describe divisors
multiplicative.
𝟏𝟎𝟐 = 𝟏𝟎𝟎 ≡ 𝟏𝟎𝟎 − 𝟗𝟑 If 𝐠𝐜𝐝(𝒎, 𝒏) = 𝟏, then each
= 𝟕 (𝐦𝐨𝐝 𝟑𝟏). divisor of 𝒎𝒏 can be written
Ques 12: If 𝒑 is an odd
Compute 𝟏𝟎 : 𝟒 uniquely as prime, prove that there exist
𝟏𝟎𝟒 = (𝟏𝟎𝟐 )𝟐 ≡ 𝟕𝟐 = 𝟒𝟗 𝒅 = 𝒅𝟏 𝒅𝟐 , integers 𝒂, 𝒃, 𝒉 such that
≡ 𝟒𝟗 − 𝟑𝟏 where 𝒂𝟐 + 𝒃𝟐 + 𝟏 = 𝒉𝒑,
= 𝟏𝟖 (𝐦𝐨𝐝 𝟑𝟏). 𝒅𝟏 ∣ 𝒎 and 𝒅𝟐 ∣ 𝒏. with
Compute 𝟏𝟎 : 𝟖 Since prime factors of 𝒎 and 𝒏 𝒑
𝟏𝟎𝟖 = (𝟏𝟎𝟒 )𝟐 ≡ 𝟏𝟖𝟐 = 𝟑𝟐𝟒. are disjoint, the mapping 𝟎≤𝒂< , 𝟎≤𝒃
(𝒅𝟏 , 𝒅𝟐 ) ↔ 𝒅𝟏 𝒅𝟐
𝟐
Reduce: 𝒑
𝟑𝟐𝟒 − 𝟑𝟏𝟎 = 𝟏𝟒 (𝐦𝐨𝐝 𝟑𝟏). is one-to-one. < , 𝟎<𝒉
Step 2: Count divisors 𝟐
Now use decomposition:
 Number of divisors of 𝒎 =
< 𝒑.
𝟏𝟎𝟏𝟏 = 𝟏𝟎𝟖 ⋅ 𝟏𝟎𝟐 ⋅ 𝟏𝟎𝟏 . This is a classical number theory
We already have: 𝝉(𝒎)
result based on the Pigeonhole
 𝟏𝟎𝟖 ≡ 𝟏𝟒  Number of divisors of 𝒏 =
Principle.
 𝟏𝟎𝟐 ≡ 𝟕 𝝉(𝒏)
We want to show that we can
 𝟏𝟎 ≡ 𝟏𝟎 Each divisor of 𝒎 can pair with
always find such integers for any
Compute: each divisor of 𝒏.
odd prime 𝒑.
𝟏𝟎𝟏𝟏 ≡ 𝟏𝟒 ⋅ 𝟕 ⋅ 𝟏𝟎. Thus total divisors of 𝒎𝒏 are:
Step 1: Construct a special set of
First: 𝝉(𝒎𝒏) = 𝝉(𝒎)𝝉(𝒏). numbers
So 𝝉(𝒏) is multiplicative. Consider the 𝒑 numbers:
 𝟎𝟐 + 𝟏, 𝟏𝟐 + 𝟏, 𝟐𝟐 + 𝟏, … , (𝒑 𝒌𝟏 = 𝒌𝟐 or 𝒌𝟏 + 𝒌𝟐 = 𝒑. always has a solution, and
− 𝟏)𝟐 + 𝟏. But they are distinct, so: moreover this solution is unique
So the list is: 𝒌𝟏 + 𝒌𝟐 = 𝒑. modulo the product
𝟏, 𝟐, 𝟓, 𝟏𝟎, … , (𝒑 − 𝟏)𝟐 + 𝟏. Let: 𝑴 = 𝒎 𝟏 𝒎𝟐 ⋯ 𝒎 𝒌 .
Each of these numbers, when 𝒂 = 𝒌𝟏 , 𝒃 = 𝒌𝟐 . Construction of the solution:
divided by 𝒑, gives a remainder in Then: Define
the set: 𝒂 + 𝒃 = 𝒑, 𝟎 ≤ 𝒂, 𝒃 < 𝒑. 𝑴
𝑴 = 𝒎 𝟏 𝒎𝟐 ⋯ 𝒎 𝒌 , 𝑴𝒊 = .
{𝟏, 𝟐, … , 𝒑}. Compute: 𝒎𝒊
There are exactly p numbers and 𝒂𝟐 + 𝒃𝟐 + 𝟏 = 𝒉𝒑. Since the moduli are pairwise
p possible remainders mod 𝒑. Check constraints: coprime, we also have
Step 2: Apply Pigeonhole  Since 𝒂 + 𝒃 = 𝒑, at least 𝐠𝐜𝐝(𝑴𝒊 , 𝒎𝒊 ) = 𝟏.
𝒑
Principle one of 𝒂 or 𝒃 is ≤ . Because of this gcd condition,
𝟐
For each number 𝒌𝟐 + 𝟏, let each 𝑴𝒊 has a multiplicative
 We can renumber the pair
𝒓𝒌 ≡ 𝒌𝟐 + 𝟏 (𝐦𝐨𝐝 𝒑), 𝟎 ≤ 𝒓𝒌 inverse modulo 𝒎𝒊 . Thus, for
so that:
< 𝒑. 𝒑 𝒑 each 𝒊, there exists a unique
Since there are exactly 𝒑 values 𝟎≤𝒂< , 𝟎≤𝒃< . integer 𝑵𝒊 such that
𝟐 𝟐
and exactly 𝒑 possible The value of 𝒉 satisfies 𝟎 < 𝒉 < 𝒑 𝑴𝒊 𝑵𝒊 ≡ 𝟏 (𝐦𝐨𝐝 𝒎𝒊 ).
remainders, by the pigeonhole because: This follows from Bezout’s
principle: 𝒂𝟐 + 𝒃𝟐 + 𝟏 < 𝒑𝟐 . identity or from the general
 two of these numbers Thus: theory of inverses in modular
must satisfy 𝒂𝟐 + 𝒃 𝟐 + 𝟏 arithmetic when two numbers are
𝒌𝟐𝟏 + 𝟏 ≡ 𝒌𝟐𝟐 + 𝟏 (𝐦𝐨𝐝 𝒑) 𝟎<𝒉= < 𝒑. coprime.
𝒑
or Now consider the number
Final Conclusion 𝒌
 some number gives For any odd prime 𝒑, we can
𝒙= 𝒂𝒊 𝑴𝒊 𝑵𝒊 .
remainder 0. always find integers 𝒂, 𝒃, 𝒉 such
𝒊 𝟏
Both cases lead to a solution. that: We claim that this 𝒙 satisfies
Case 1: Some 𝒌 satisfies 𝒌𝟐 + 𝟏 ≡ 𝒂𝟐 + 𝒃𝟐 + 𝟏 = 𝒉𝒑, every congruence in the system.
𝟎 (𝐦𝐨𝐝 𝒑) with Verification:
Then: 𝒑 𝒑
𝟎≤𝒂< , 𝟎≤𝒃< , 𝟎<𝒉 Fix an index 𝒋. Reduce the
𝒌𝟐 + 𝟏 = 𝒉𝒑 𝟐 𝟐 expression for 𝒙 modulo 𝒎𝒋 :
for some integer 𝒉. < 𝒑.
Thus the required integers 𝒙
Set: ≡ 𝒂𝒋 𝑴𝒋 𝑵𝒋
𝒂 = 𝒌, 𝒃 = 𝟎. exist for every odd prime 𝒑.
This satisfies the form: This completes the proof. + 𝒂𝒊 𝑴𝒊 𝑵𝒊 (𝐦𝐨𝐝 𝒎𝒋 ).
𝒂𝟐 + 𝒃𝟐 + 𝟏 = 𝒉𝒑. 𝒊 𝒋
This already gives a solution. For every 𝒊 ≠ 𝒋, note that 𝑴𝒊
Case 2: No remainder is 0 (more Question 1 State and contains the full factor 𝒎𝒋 , since
general case) 𝒎𝟏 𝒎𝟐 ⋯ 𝒎 𝒌
By pigeonhole, two numbers have
Prove the Chinese 𝑴𝒊 =
𝒎𝒊
,
the same remainder: Remainder Theorem and thus 𝒎𝒋 ∣ 𝑴𝒊 . Therefore,
𝒌𝟐𝟏 + 𝟏 ≡ 𝒌𝟐𝟐 + 𝟏 (𝐦𝐨𝐝 𝒑) Solution =Let 𝒎𝟏 , 𝒎𝟐 , … , 𝒎𝒌 be 𝑴𝒊 ≡ 𝟎 (𝐦𝐨𝐝 𝒎𝒋 ).
Subtract: pairwise coprime positive Hence all the terms with 𝒊 ≠ 𝒋
𝒌𝟐𝟏 ≡ 𝒌𝟐𝟐 (𝐦𝐨𝐝 𝒑) integers, meaning that vanish modulo 𝒎𝒋 , leaving
This gives: 𝐠𝐜𝐝(𝒎𝒊 , 𝒎𝒋 ) = 𝟏 whenever 𝒊
𝒙 ≡ 𝒂𝒋 𝑴𝒋 𝑵𝒋 (𝐦𝐨𝐝 𝒎𝒋 ).
(𝒌𝟏 − 𝒌𝟐 )(𝒌𝟏 + 𝒌𝟐 ) ≡ 𝟎 (𝐦𝐨𝐝 𝒑). ≠ 𝒋.
But by construction, 𝑴𝒋 𝑵𝒋 ≡
Because 𝒑 is prime, we must Consider the system of linear
congruences 𝟏 (𝐦𝐨𝐝 𝒎𝒋 ). Therefore,
have:
𝒌𝟏 ≡ 𝒌𝟐 (𝐦𝐨𝐝 𝒑) or 𝒌𝟏 𝒙 ≡ 𝒂𝟏 (𝐦𝐨𝐝 𝒎𝟏 ), 𝒙 𝒙 ≡ 𝒂𝒋 (𝐦𝐨𝐝 𝒎𝒋 ).
≡ −𝒌𝟐 (𝐦𝐨𝐝 𝒑). ≡ 𝒂𝟐 (𝐦𝐨𝐝 𝒎𝟐 ), … , 𝒙 So the constructed 𝒙 satisfies all
Since the chosen values satisfy ≡ 𝒂𝒌 (𝐦𝐨𝐝 𝒎𝒌 ). the congruences simultaneously.
𝟎 ≤ 𝒌𝒊 < 𝒑, The Chinese Remainder Theorem Uniqueness of the solution:
this forces: (CRT) asserts that such a system Assume 𝒙 and 𝒚 are two solutions
of the system. Then
 𝒙 ≡ 𝒚 (𝐦𝐨𝐝 𝒎𝒊 ) for all 𝒊. characterizes the Möbius invertible and that the Möbius
This implies that each 𝒎𝒊 divides function: function provides the precise
the difference 𝒙 − 𝒚. Since the 𝟏 if 𝒏 = 𝟏, arithmetic inverse needed.
𝝁 (𝒅) =
moduli 𝒎𝟏 , 𝒎𝟐 , … , 𝒎𝒌 are 𝟎 if 𝒏 > 𝟏. Thus the Möbius Inversion
𝒅∣𝒏
pairwise coprime, their product This identity expresses the fact Formula is completely proved.
𝑴 = 𝒎 𝟏 𝒎𝟐 ⋯ 𝒎 𝒌 that the Möbius function is the Question 3 State and
also divides 𝒙 − 𝒚. Hence,
𝒙 ≡ 𝒚 (𝐦𝐨𝐝 𝑴).
inverse of the constant function 𝟏 Prove Hurwitz’s
under Dirichlet convolution.
Thus any two solutions differ only Now assume that
Theorem
by a multiple of the product of all Solution =Hurwitz’s Theorem is a
moduli, establishing the 𝒈(𝒏) = 𝒇 (𝒅), classical result in number theory
uniqueness of the solution modulo 𝒅∣𝒏 and the theory of quadratic
𝑴. that is, 𝒈 is the Dirichlet forms. It states a precise
This completes the proof of the convolution 𝒈 = 𝒇 ∗ 𝟏. condition under which an integer
Chinese Remainder Theorem. To invert this relation, multiply can be written as a sum of two
both sides of the defining squares, and in a more algebraic
Question 2 State and equation by 𝝁(𝒌) and sum over form it describes divisibility
Prove the Möbius all positive divisors 𝒌 ∣ 𝒏: relations within sums of two
𝒏
Inversion Formula 𝝁 (𝒌) 𝒈 squares.
Solution =Let 𝒇 and 𝒈 be 𝒌 The standard version of
𝒌∣𝒏
arithmetic functions defined on Hurwitz’s theorem states:
= 𝝁 (𝒌) 𝒇 (𝒅). If an integer 𝒏 divides a sum of
the set of positive integers. The
Möbius inversion formula gives a
𝒌∣𝒏 𝒅∣(𝒏/𝒌) two squares
In the right-hand side, each term 𝒂𝟐 + 𝒃 𝟐 ,
method for recovering 𝒇 from
𝒅 ∣ 𝒏/𝒌 can be rewritten by and every prime divisor 𝒑 of 𝒏
knowledge of 𝒈, whenever the two
introducing the variable 𝒎 such satisfying 𝒑 ≡ 𝟑 (𝐦𝐨𝐝 𝟒) appears
are related by a divisor-sum
that 𝒌𝒎 = 𝒏/𝒅. Thus the in the factorization of 𝒏 with an
relation.
expression becomes even exponent, then there exist
The statement is as follows:
If 𝝁 (𝒌) 𝒇 (𝒅) integers 𝒙 and 𝒚 such that
𝒈(𝒏) = 𝒇 (𝒅), 𝒌∣𝒏 𝒅∣(𝒏/𝒌) 𝒏 = 𝒙 𝟐 + 𝒚𝟐 .
= 𝒇 (𝒅) 𝝁 (𝒌). Equivalently, the theorem asserts
𝒅∣𝒏
then the function 𝒇(𝒏) can be that a positive integer 𝒏 is
𝒅∣𝒏 𝒌∣(𝒏/𝒅)
uniquely recovered from 𝒈(𝒏) Now examine the inner sum expressible as the sum of two
using squares if and only if in the prime
𝒏 𝝁 (𝒌). factorization of 𝒏, every prime
𝒇(𝒏) = 𝝁 (𝒅) 𝒈 , 𝒌∣(𝒏/𝒅) 𝒑 ≡ 𝟑 (𝐦𝐨𝐝 𝟒) appears with even
𝒅
𝒅∣𝒏 If 𝒏/𝒅 = 𝟏, the sum equals 𝟏. If multiplicity.
where 𝝁(𝒅) denotes the Möbius 𝒏/𝒅 > 𝟏, the sum equals 𝟎
function, which is defined by because 𝒏/𝒅 has some prime Proof:
𝝁(𝒅) factorization whose divisors force Let the prime factorization of 𝒏
𝟏 if 𝒅 = 𝟏, cancellation in the Möbius sum. be
⎧ 𝒌
⎪(−𝟏) if 𝒅 is a product of 𝒌, This follows from the defining 𝒏
= 𝒅𝒊𝒔𝒕𝒊𝒏𝒄𝒕 𝒑 𝒑𝒓𝒊𝒎𝒆𝒔 property of 𝝁. 𝜶𝟎 𝜶𝟏 𝜶𝟐 𝜶 𝜷 𝜷 𝜷
= 𝟐 𝒑𝟏 𝒑𝟐 ⋯ 𝒑𝒌 𝒌 𝒒𝟏 𝟏 𝒒𝟐 𝟐 ⋯ 𝒒𝒎𝒎 ,
⎨𝟎 if 𝒅 is divisible by the. Thus only the term where 𝒅 = 𝒏
⎪ where
⎩ 𝒔𝒒𝒖𝒂𝒓𝒆 𝒐𝒇 𝒂 𝒑𝒓𝒊𝒎𝒆 survives, and we obtain
𝒏 𝒑𝒊 ≡ 𝟏 (𝐦𝐨𝐝 𝟒), 𝒒𝒋
This theorem is fundamental in 𝝁 (𝒌) 𝒈 = 𝒇(𝒏).
𝒌 ≡ 𝟑 (𝐦𝐨𝐝 𝟒).
number theory because it 𝒌∣𝒏 The theorem claims that
connects summatory functions Therefore, the inversion formula 𝒏 = 𝒙𝟐 + 𝒚𝟐 is possible
with their original arithmetic 𝒏
𝒇(𝒏) = 𝝁 (𝒅) 𝒈 exactly when all 𝜷𝒋 (the exponents
functions in a precise invertible 𝒅
manner. 𝒅∣𝒏 on primes 𝒒𝒋 ≡ 𝟑 (𝐦𝐨𝐝 𝟒)) are
Proof: holds for every positive integer 𝒏. even.
We start from the identity that This shows that the divisor-sum Step 1: Necessity
relation between 𝒇 and 𝒈 is Suppose
 𝒏 = 𝒙𝟐 + 𝒚𝟐 . Since both necessity and squares.
Consider a prime 𝒒 ≡ 𝟑 (𝐦𝐨𝐝 𝟒). sufficiency are established, Thus, the set of numbers
In the Gaussian integers ℤ[𝒊], the Hurwitz’s Theorem is fully representable by four squares is
norm function proved: a positive integer is a sum closed under multiplication.
𝑵(𝒂 + 𝒃𝒊) = 𝒂𝟐 + 𝒃𝟐 of two squares if and only if each Step 2: Representation of primes
is multiplicative. The number 𝒙 + prime 𝒑 ≡ 𝟑 (𝐦𝐨𝐝 𝟒) appears To represent all integers, it is
𝒊𝒚 has norm 𝒏. If a prime 𝒒 ≡ with even exponent in its enough to show that every prime
𝟑 (𝐦𝐨𝐝 𝟒) divides 𝒏, then 𝒒 factorization. number can be written as a sum
divides the norm 𝑵(𝒙 + 𝒊𝒚). In Question 4 ) State and of four squares, because any
ℤ[𝒊], such primes remain prime composite can be formed from
Prove Lagrange’s Four- products of primes, and Step 1
(they do not factor into smaller
elements). Therefore, if 𝒒 ∣ 𝑵(𝒙 + Square Theorem ensures multiplicative closure.
𝒊𝒚), then 𝒒 must divide both 𝒙 Solution =Lagrange’s Four- The essential facts are:
and 𝒚. This implies that 𝒒𝟐 ∣ 𝒙𝟐 + Square Theorem is one of the  The prime 𝟐 = 𝟏𝟐 + 𝟏𝟐 +
𝒚𝟐 . Repeating this argument central results in additive number 𝟎𝟐 + 𝟎𝟐 .
shows that primes 𝒒 ≡ 𝟑 (𝐦𝐨𝐝 𝟒) theory. It asserts that every  Any prime 𝒑 ≡ 𝟏 (𝐦𝐨𝐝 𝟒)
appear only with even exponent positive integer can be expressed is a sum of two squares,
in the factorization of 𝒏. Hence as a sum of four squares. In hence also a sum of four
the condition is necessary. precise form: squares.
Step 2: Sufficiency Every positive integer 𝒏 ∈ ℤ can  Any prime 𝒑 ≡ 𝟑 (𝐦𝐨𝐝 𝟒)
Now assume that every prime be written as cannot be written as a sum
𝒒𝒋 ≡ 𝟑 (𝐦𝐨𝐝 𝟒) appears with 𝒏 = 𝒂𝟐 + 𝒃𝟐 + 𝒄𝟐 + 𝒅𝟐 of two squares, but can be
for some integers 𝒂, 𝒃, 𝒄, 𝒅. shown (via properties of
even exponent. Thus the
This theorem shows that four quadratic residues and
factorization becomes
𝜶 squares are sufficient to represent modular arguments) to be
𝒏 = 𝟐𝜶𝟎 ∏𝒑𝒊 𝒊 ∏(𝒒𝟐𝒋 )𝜸𝒋 .
any natural number, no matter expressible as
We use the known fact that: how large or how complicated its 𝒑 = 𝒙 𝟐 + 𝒚𝟐 + 𝒛 𝟐 + 𝒘𝟐 .
 𝟐 = 𝟏𝟐 + 𝟏𝟐 , prime factorization is. Thus every prime can be
 every prime 𝒑 ≡ Proof (Outline Using Classical expressed as a sum of four
𝟏 (𝐦𝐨𝐝 𝟒) can be Number Theory): squares.
expressed as a sum of two The full proof is long and Step 3: Representation of all
squares, historically rich, but the essential integers
 every prime 𝒒 ≡ mathematical structure relies on Let
𝟑 (𝐦𝐨𝐝 𝟒) squared (i.e., several key steps involving 𝜶 𝜶
𝒏 = 𝒑𝟏 𝟏 𝒑𝟐 𝟐 ⋯ 𝒑𝒌 𝒌
𝜶
𝒒𝟐 ) is a sum of two squares properties of quadratic forms and be the prime factorization of 𝒏.
since 𝒒𝟐 = 𝒒𝟐 + 𝟎𝟐 . closure under multiplication. 𝜶
Each prime power 𝒑𝒊 𝒊 can be
Thus each factor of 𝒏 can be Step 1: The identity that
written as a sum of four squares,
individually written as a sum of preserves representation by four
because:
two squares. squares
Consider the four-square identity  A prime can be
Furthermore, the identity
(discovered by Euler), valid for represented as a sum of
(𝒂𝟐 + 𝒃𝟐 )(𝒄𝟐 + 𝒅𝟐 )
all integers 𝒂, 𝒃, 𝒄, 𝒅 and 𝒙, 𝒚, 𝒛, 𝒘: four squares.
= (𝒂𝒄 − 𝒃𝒅)𝟐
(𝒂𝟐 + 𝒃𝟐 + 𝒄𝟐 + 𝒅𝟐 )(𝒙𝟐 + 𝒚𝟐 + 𝒛𝟐  The four-square identity
+ (𝒂𝒅 + 𝒃𝒄)𝟐
ensures that the product of
shows that the product of two + 𝒘𝟐 )
two such representations is
numbers expressible as sums of = (𝒂𝒙 − 𝒃𝒚 − 𝒄𝒛 − 𝒅𝒘)𝟐 + (𝒂𝒚
again a sum of four
two squares is again a sum of two + 𝒃𝒙 + 𝒄𝒘 − 𝒅𝒛)𝟐 squares.
squares. Applying this identity +(𝒂𝒛 − 𝒃𝒘 + 𝒄𝒙 + 𝒅𝒚)𝟐
 Therefore,
repeatedly, we conclude that the + (𝒂𝒘 + 𝒃𝒛 − 𝒄𝒚 𝜶
product of all the above factors 𝒑𝒊 𝒊 = 𝒙𝟐𝒊 + 𝒚𝟐𝒊 + 𝒛𝟐𝒊 + 𝒘𝟐𝒊
+ 𝒅𝒙)𝟐 .
gives for some integers
This identity shows that the
𝒏 = 𝒙𝟐 + 𝒚𝟐 . 𝒙 𝒊 , 𝒚𝒊 , 𝒛 𝒊 , 𝒘𝒊 .
product of two numbers each
Therefore, the condition is Now multiply these
expressible as a sum of four
sufficient. representations:
squares is again a sum of four
 𝒌 2. Derivation through Continued arises naturally from
𝜶
𝒏= 𝒑𝒊 𝒊 . Fractions approximations to √𝑫,
𝒊 𝟏 A rigorous derivation uses the particularly from convergents in
Using Euler’s identity repeatedly, continued fraction expansion of its continued fraction expansion.
we conclude that the product of √𝑫. The continued fraction method
all these representations is itself a Since √𝑫 is irrational, its guarantees the existence of a
sum of four squares. Hence continued fraction expansion is fundamental solution, and then
𝒏 = 𝒂𝟐 + 𝒃𝟐 + 𝒄𝟐 + 𝒅𝟐 periodic: infinitely many solutions follow
for suitable integers 𝒂, 𝒃, 𝒄, 𝒅. √𝑫 = [𝒂𝟎 ; 𝒂𝟏 , 𝒂𝟐 , … , 𝒂𝒌 ]. using powers of the fundamental
Conclusion: Let unit in ℤ[√𝑫].
Every positive integer can be 𝒑𝒏 Thus Pell’s equation is fully
expressed as a sum of four 𝒒𝒏 derived and its structure
squares. The closure under be the 𝒏-th convergent of this explained.
multiplication together with the
ability to represent every prime
continued fraction. These Question 6 )State and
convergents satisfy the
by four squares completes the approximation inequality:
Prove the Quadratic
proof of Lagrange’s Four-Square 𝒑𝒏 𝟏 Reciprocity Theorem
Theorem. √𝑫 − < 𝟐. Solution =Let 𝒑 and 𝒒 be two
𝒒𝒏 𝒒𝒏
Question 5)Derive Pell’s Rewrite this: distinct odd primes. The
Equation in Number 𝒑𝟐𝒏 − 𝑫𝒒𝟐𝒏 < 𝟏. Quadratic Reciprocity Law,
discovered by Gauss, describes a
Theory Because the left-hand side is an
deep relationship between the
Solution =Pell’s equation is one of integer, the only possibility is
solvability of the two quadratic
the most fundamental 𝒑𝟐𝒏 − 𝑫𝒒𝟐𝒏 = ±𝟏.
congruences
Diophantine equations in number When the period of the continued
𝒙𝟐 ≡ 𝒑 (𝐦𝐨𝐝 𝒒) and 𝒙𝟐
theory. It has the general form fraction has even length, we get
≡ 𝒒 (𝐦𝐨𝐝 𝒑).
𝒙𝟐 − 𝑫𝒚𝟐 = 𝟏, 𝒑𝟐𝒏 − 𝑫𝒒𝟐𝒏 = 𝟏.
The theorem is stated in terms of
where 𝑫 is a positive integer that This gives the fundamental
the Legendre symbol
is not a perfect square. The goal is solution (𝒙𝟏 , 𝒚𝟏 ). 𝒂
to derive this equation and Thus Pell’s equation emerges
𝒑
understand why it has infinitely naturally from the continued 𝟏, if 𝒂 is a quadratic residue m
many integer solutions (𝒙, 𝒚). fraction approximations to √𝑫. =
−𝟏, if 𝒂 is a non-residue mod 𝒑
1. Origin of Pell’s Equation 3. Infinitely Many Solutions Quadratic Reciprocity Theorem
Let 𝑫 be a positive non-square If (𝒙𝟏 , 𝒚𝟏 ) is the fundamental (Statement)
integer. Consider the irrational solution of For distinct odd primes 𝒑 and 𝒒,
number √𝑫. 𝒙𝟐 − 𝑫𝒚𝟐 = 𝟏, 𝒑 𝒒 (𝒑 𝟏) (𝒒 𝟏)
then all other solutions come from = (−𝟏) 𝟐 ⋅ 𝟐 .
The best approximations to √𝑫 𝒒 𝒑
come from solutions to powers of Equivalently,
𝒙 − 𝒚√𝑫 as small as possible. 𝒙𝟏 + 𝒚𝟏 √𝑫.  If either 𝒑 ≡ 𝟏 (𝐦𝐨𝐝 𝟒) or
Rewriting this expression, we get Let 𝒒 ≡ 𝟏 (𝐦𝐨𝐝 𝟒), then
𝒙 − 𝒚√𝑫 ≈ 𝟎 ⇒ 𝒙 ≈ 𝒚√𝑫. 𝒙𝒏 + 𝒚𝒏 √𝑫 = (𝒙𝟏 + 𝒚𝟏 √𝑫)𝒏 . 𝒑 𝒒
Expanding using the binomial = .
Square both sides: 𝒒 𝒑
theorem and equating rational  If both 𝒑 ≡ 𝟑 (𝐦𝐨𝐝 𝟒) and
𝒙𝟐 ≈ 𝑫𝒚𝟐 .
and irrational parts, we obtain 𝒒 ≡ 𝟑 (𝐦𝐨𝐝 𝟒), then
Thus the integer approximation
infinitely many integer pairs 𝒑 𝒒
naturally leads to the Diophantine =− .
(𝒙𝒏 , 𝒚𝒏 ) satisfying
form 𝒒 𝒑
𝒙𝟐𝒏 − 𝑫𝒚𝟐𝒏 = 𝟏. This is the fundamental relation
𝒙𝟐 − 𝑫𝒚𝟐 ≈ 𝟎.
Hence the equation has infinitely governing quadratic residues.
But for exact integer solutions
many solutions, all generated Proof (Gauss’s Lemma
with 𝒙, 𝒚 ∈ ℤ, the closest possible
from the fundamental solution. Approach)
value is
Conclusion We use Gauss’s Lemma, which
𝒙𝟐 − 𝑫𝒚𝟐 = 𝟏.
Pell’s equation states:
This is the classical Pell equation.
𝒙𝟐 − 𝑫𝒚𝟐 = 𝟏
For an odd prime 𝒑, and integer Conclusion So start with 𝒙 = 𝟕𝟖:
𝒂 coprime to 𝒑, consider the set Thus, we have shown that the  𝟕𝟖𝟐 − 𝟓𝟗𝟓𝟗 = 𝟔𝟎𝟖𝟒 −
𝒑−𝟏 solvability of 𝟓𝟗𝟓𝟗 = 𝟏𝟐𝟓 (not a
𝒂, 𝟐𝒂, 𝟑𝒂, … , 𝒂
𝟐 𝒙𝟐 ≡ 𝒑 (𝐦𝐨𝐝 𝒒) and 𝒙𝟐 perfect square)
reduced modulo 𝒑 into the ≡ 𝒒 (𝐦𝐨𝐝 𝒑) Next 𝒙 = 𝟕𝟗:
interval (−𝒑/𝟐, 𝒑/𝟐]. are deeply related, and Quadratic  𝟕𝟗𝟐 − 𝟓𝟗𝟓𝟗 = 𝟔𝟐𝟒𝟏 −
Let 𝒏(𝒂) be the number of these Reciprocity gives the exact 𝟓𝟗𝟓𝟗 = 𝟐𝟖𝟐 (not a
reduced values that are negative. relationship. This theorem is one perfect square)
Then of the cornerstones of higher
Next 𝒙 = 𝟖𝟎:
𝒂
= (−𝟏)𝒏(𝒂) .Applying Gauss’s number theory and was described
𝒑  𝟖𝟎𝟐 − 𝟓𝟗𝟓𝟗 = 𝟔𝟒𝟎𝟎 −
by Gauss as the "gem of
Lemma to Both Primes arithmetic." 𝟓𝟗𝟓𝟗 = 𝟒𝟒𝟏 = 𝟐𝟏𝟐
Apply Gauss’s Lemma to This completes the derivation and So 𝒙 = 𝟖𝟎, 𝒚 = 𝟐𝟏.
compute proof of the Quadratic Hence
𝒒 𝒑 𝟓𝟗𝟓𝟗 = (𝟖𝟎 − 𝟐𝟏)(𝟖𝟎 + 𝟐𝟏)
= (−𝟏)𝑵𝟏 , Reciprocity Theorem.
𝒑 𝒒 = 𝟓𝟗 ⋅ 𝟏𝟎𝟏.
Question 7) Discuss Fermat’s
= (−𝟏)𝑵𝟐 , Thus Fermat’s factorization
where Factorization Method with method works effectively when
 𝑵𝟏 = number of negatives Example and Prove that the two factors are close.
in the set Fermat Number 𝑭𝟓 is 3. Prove that Fermat Number 𝑭𝟓
𝒑−𝟏 Divisible by 641 is Divisible by 641
𝒒, 𝟐𝒒, … , 𝒒 (𝐦𝐨𝐝 𝒑) Fermat numbers are defined by
𝟐 Solution =Fermat’s factorization 𝒏
 𝑵𝟐 = number of negatives method is based on the idea that 𝑭𝒏 = 𝟐𝟐 + 𝟏.
in the set any odd integer 𝑵 can be So
𝒒−𝟏 expressed as a difference of two 𝑭𝟓 = 𝟐𝟑𝟐 + 𝟏 = 𝟒𝟐𝟗𝟒𝟗𝟔𝟕𝟐𝟗𝟕.
𝒑, 𝟐𝒑, … , 𝒑 (𝐦𝐨𝐝 𝒒).
𝟐 squares: We will show
Hence 𝑵 = 𝒙𝟐 − 𝒚𝟐 = (𝒙 − 𝒚)(𝒙 + 𝒚). 𝟔𝟒𝟏 ∣ 𝑭𝟓 .
𝒑 𝒒 Step 1: Use special identities for
= (−𝟏)𝑵𝟏 𝑵𝟐 . This method works best when 𝑵
𝒒 𝒑 has two factors close to each 641
Counting the Number of Negative other. Observe that
Reductions 1. Fermat’s Factorization Method 𝟔𝟒𝟏 = 𝟔𝟒𝟎 + 𝟏 = 𝟓 ⋅ 𝟐𝟕 + 𝟏.
We use the fact that for integers (Explanation) Another useful identity is
𝒂, the inequality For an odd integer 𝑵, write 𝟔𝟒𝟏 = 𝟔𝟐𝟓 + 𝟏𝟔 = 𝟐𝟓𝟐 + 𝟒𝟐 .
𝒑
𝒒𝒂 > mod 𝒑 𝑵 = 𝒙𝟐 − 𝒚𝟐 . Step 2: Show 𝟐𝟑𝟐 ≡
𝟐 Rearranging gives −𝟏 (𝐦𝐨𝐝 𝟔𝟒𝟏)
corresponds to negative
𝒙𝟐 = 𝑵 + 𝒚𝟐 . We use the fact that
reduction.
We begin with 𝟔𝟒𝟏 = 𝟓 ⋅ 𝟐𝟕 + 𝟏.
A classical result in number
𝒙 = √𝑵 Compute
theory gives
(𝒑 − 𝟏)(𝒒 − 𝟏) and check whether 𝟐𝟕 = 𝟏𝟐𝟖.
𝑵𝟏 + 𝑵𝟐 = . 𝒙𝟐 − 𝑵 Then
𝟒
Putting this into the Legendre is a perfect square. 𝟏𝟐𝟖𝟓 = (𝟐𝟕 )𝟓 = 𝟐𝟑𝟓 .
symbol product: If Now reduce modulo 641:
𝒑 𝒒 (𝒑 𝟏)(𝒒 𝟏) 𝒙𝟐 − 𝑵 = 𝒚𝟐 ,  Note that
= (−𝟏) 𝟒 . then we have factored 𝑵 as 𝟏𝟐𝟖 ≡ −𝟓𝟏𝟑 (𝐦𝐨𝐝 𝟔𝟒𝟏)
𝒒 𝒑
Note 𝑵 = (𝒙 − 𝒚)(𝒙 + 𝒚). but we use a better trick:
(𝒑 − 𝟏)(𝒒 − 𝟏) We keep increasing 𝒙 until we We rewrite 641 as
find a suitable 𝒚. 𝟔𝟒𝟏 = 𝟔𝟐𝟓 + 𝟏𝟔 = 𝟐𝟓𝟐 + 𝟒𝟐 .
𝟒
(𝒑 − 𝟏) (𝒒 − 𝟏) This is the classical Fermat Compute the following:
= ⋅ , method. 𝟐𝟑𝟐 = (𝟐𝟒 )𝟖 = 𝟏𝟔𝟖 .
𝟐 𝟐
hence the quadratic reciprocity 2. Example of Fermat’s Method 𝟏𝟔 ≡ −𝟔𝟐𝟓 (𝐦𝐨𝐝 𝟔𝟒𝟏).
formula follows exactly: Factor 𝑵 = 𝟓𝟗𝟓𝟗. 𝟏𝟔 ≡ −𝟐𝟓𝟐 (𝐦𝐨𝐝 𝟔𝟒𝟏).
𝒑 𝒒 (𝒑 𝟏) (𝒒 𝟏) Compute Thus
= (−𝟏) 𝟐 ⋅ 𝟐 . √𝟓𝟗𝟓𝟗 ≈ 𝟕𝟕. 𝟏𝟖.
𝒒 𝒑
 𝟏𝟔𝟖 ≡ (−𝟐𝟓𝟐 )𝟖 = (−𝟏)𝟖 ⋅ 𝟐𝟓𝟏𝟔 They satisfy the inequality Conclusion
= 𝟐𝟓𝟏𝟔 (𝐦𝐨𝐝 𝟔𝟒𝟏). 𝒑𝒏 𝟏 For any irrational number 𝜶, the
𝜶− < 𝟐 .
Another identity is 𝒒𝒏 𝒒𝒏 𝒂𝒏 𝟏 sequence of continued fraction
𝒑
𝟐𝟓 ≡ −𝟒𝟐 (𝐦𝐨𝐝 𝟔𝟒𝟏). Since each 𝒂𝒏 𝟏 ≥ 𝟏, we always convergents 𝒏 gives infinitely
𝒒𝒏
Using these reductions repeatedly have many rational approximations
one obtains 𝒑𝒏 𝟏
𝜶− < 𝟐. such that
𝟐𝟑𝟐 ≡ −𝟏 (𝐦𝐨𝐝 𝟔𝟒𝟏). 𝒒𝒏 𝒒𝒏 𝒂 𝟏
Hence But Hurwitz improved this to a 𝜶− < .
𝒃 √𝟓𝒃𝟐
𝟐𝟑𝟐 + 𝟏 ≡ 𝟎 (𝐦𝐨𝐝 𝟔𝟒𝟏). stronger inequality. This completes the proof that
Conclusion 2. Hurwitz’s Theorem irrational numbers can always be
Since Hurwitz proved that for every approximated infinitely often
𝟐𝟑𝟐 + 𝟏 ≡ 𝟎 (𝐦𝐨𝐝 𝟔𝟒𝟏), irrational number 𝜶, the with such precision.
we conclude that inequality
𝟔𝟒𝟏 ∣ 𝑭𝟓 . 𝒂 𝟏 Question 9) Solve the
𝜶− <
Thus Fermat number 𝑭𝟓 is 𝒃 √𝟓𝒃𝟐 congruence 𝟑𝒙𝟐 + 𝟓𝒙 +
composite, and Fermat’s has infinitely many solutions in 𝟗 ≡ 𝟎 (𝐦𝐨𝐝 𝟏𝟏).
factorization method combined integers 𝒂 and 𝒃. Solution =
with modular arithmetic confirms The only exception is when 𝜶 is We must find all integers 𝒙 (mod
that 641 is a divisor of 𝑭𝟓 . an irrational number equivalent 11) satisfying
Question 8 )If 𝜶 is an to the golden ratio 𝟑𝒙𝟐 + 𝟓𝒙 + 𝟗 ≡ 𝟎 (𝐦𝐨𝐝 𝟏𝟏).
irrational number, then 𝟏 + √𝟓 Since we are working modulo a
𝝓= ,
there are infinitely many 𝟐 prime (11), we can solve it by
𝒂 in which the constant 𝟏/√𝟓 is best completing the square or by using
rational numbers such that
𝒃 possible. the discriminant.
𝒂 𝟏 𝟏 3. Proof Outline Using the 1. Write the quadratic
𝜶− < ⋅ .
𝒃 √𝟓 𝒃𝟐 Recurrence Relation of congruence
Solution =This is a classical result Convergents 𝟑𝒙𝟐 + 𝟓𝒙 + 𝟗 ≡
from Diophantine approximation, The convergents satisfy 𝟎 (𝐦𝐨𝐝 𝟏𝟏).Since 𝟑 is invertible
closely related to Hurwitz’s 𝒑𝒏 𝟏 = 𝒂 𝒏 𝟏 𝒑𝒏 + 𝒑 𝒏 𝟏 , 𝒒𝒏 𝟏 modulo 𝟏𝟏, multiply both sides by
Theorem, which gives an optimal = 𝒂𝒏 𝟏 𝒒𝒏 + 𝒒𝒏 𝟏 . the inverse of 𝟑 modulo 𝟏𝟏.
constant for how well irrational For convergents, we know The inverse of 𝟑 (𝐦𝐨𝐝 𝟏𝟏)
numbers can be approximated by 𝒑𝒏 𝟏 satisfies
𝜶− < .
rationals. 𝒒𝒏 𝒒𝒏 𝒒𝒏 𝟏 𝟑𝒌 ≡ 𝟏 (𝐦𝐨𝐝 𝟏𝟏).
We want to show: For any Since Checking values we find
irrational 𝜶, there exist infinitely 𝒒𝒏 𝟏 ≥ 𝒂𝒏 𝟏 𝒒𝒏 , 𝟑 ⋅ 𝟒 = 𝟏𝟐 ≡ 𝟏 (𝐦𝐨𝐝 𝟏𝟏).
𝒂
many rational numbers with we get So the inverse of 𝟑 is 𝟒.
𝒃
𝒂 𝟏 𝒑𝒏 𝟏 Multiply entire equation by 𝟒:
𝜶− < .
𝜶− < . 𝒒𝒏 𝒂𝒏 𝟏 𝒒𝟐𝒏 𝟒(𝟑𝒙𝟐 + 𝟓𝒙 + 𝟗) ≡ 𝟎 (𝐦𝐨𝐝 𝟏𝟏).
𝒃 √𝟓𝒃𝟐
Hurwitz proved (after studying This gives
1. Use Continued Fraction
Expansion the sequence 𝒂𝒏 ) that for 𝟏𝟐𝒙𝟐 + 𝟐𝟎𝒙 + 𝟑𝟔 ≡ 𝟎 (𝐦𝐨𝐝 𝟏𝟏).
Every irrational number 𝜶 has an infinitely many 𝒏, we have Reduce each term modulo 11:
infinite continued fraction 𝒂𝒏 𝟏 ≥ √𝟓. 𝟏𝟐𝒙𝟐 ≡ 𝒙𝟐 , 𝟐𝟎𝒙 ≡ 𝟗𝒙, 𝟑𝟔
expansion Thus ≡ 𝟑.
𝜶 = [𝒂𝟎 ; 𝒂𝟏 , 𝒂𝟐 , 𝒂𝟑 , … ]. 𝒑𝒏 𝟏 Thus the equation becomes
𝜶− < . 𝒙𝟐 + 𝟗𝒙 + 𝟑 ≡ 𝟎 (𝐦𝐨𝐝 𝟏𝟏).
Let 𝒒𝒏 𝒒𝟐𝒏 √𝟓
𝒑𝒏 Hence infinitely many 2. Solve using discriminant
𝒒𝒏 convergents satisfy the desired A quadratic 𝒙𝟐 + 𝒃𝒙 + 𝒄 ≡
denote the 𝒏-th convergent of this inequality 𝟎 (𝐦𝐨𝐝 𝒑) has solutions
continued fraction. These 𝒂 𝟏 −𝒃 ± √𝒃𝟐 − 𝟒𝒄
convergents give the best rational 𝜶− < . 𝒙≡ (𝐦𝐨𝐝 𝒑).
𝒃 √𝟓𝒃𝟐 𝟐
approximations to 𝜶 in a precise Here
sense. 𝒃 = 𝟗, 𝒄 = 𝟑, 𝒑 = 𝟏𝟏.
Compute the discriminant: These are the two distinct Not all of 𝒙, 𝒚, 𝒛 are zero.
𝚫 = 𝒃𝟐 − 𝟒𝒄 = 𝟗𝟐 − 𝟏𝟐 solutions modulo 11. Thus
= 𝟖𝟏 − 𝟏𝟐 = 𝟔𝟗. Question 10) Prove that a 𝒙𝟐 + 𝒚𝟐 + 𝒛𝟐 = 𝒌𝒑
Reduce modulo 11: prime 𝒑 can be expressed as for some integer 𝒌, with
𝟔𝟗 ≡ 𝟔𝟗 − 𝟔𝟔 = 𝟑 (𝐦𝐨𝐝 𝟏𝟏). the sum of four squares. 𝟏 ≤ 𝒌 ≤ 𝟑𝒑.
Thus Solution =We must show that 3. Choose the smallest such 𝒌
𝚫 ≡ 𝟑 (𝐦𝐨𝐝 𝟏𝟏). every prime number 𝒑 can be We have a representation
We need to check whether 3 is a written in the form 𝒌𝒑 = 𝒙𝟐 + 𝒚𝟐 + 𝒛𝟐 .
quadratic residue modulo 11. Let 𝒌𝟎 be the smallest positive
𝒑 = 𝒂𝟐 + 𝒃𝟐 + 𝒄𝟐 + 𝒅𝟐 ,
Test squares modulo 11: integer for which this is possible.
for some integers 𝒂, 𝒃, 𝒄, 𝒅.
𝟎𝟐 = 𝟎, 𝟏𝟐 = 𝟏, 𝟐𝟐 = 𝟒, 𝟑𝟐 We now show that 𝒌𝟎 = 𝟏, which
This is a special case of
= 𝟗, 𝟒𝟐 = 𝟓, 𝟓𝟐 Lagrange’s Four-Square means
= 𝟑. Theorem, but we will give a direct 𝒑 = 𝒂𝟐 + 𝒃𝟐 + 𝒄𝟐 .
We see 𝟓𝟐 ≡ 𝟑 (𝐦𝐨𝐝 𝟏𝟏). argument specifically for prime But even if 𝒌𝟎 > 𝟏, we will show it
Thus numbers. leads to a contradiction using
√𝟑 ≡ ±𝟓 (𝐦𝐨𝐝 𝟏𝟏). 1. Use Euler’s Four-Square descent.
3. Substitute into quadratic Identity 4. Apply descent to show 𝒌𝟎 = 𝟏
formula Euler discovered the identity Suppose, for contradiction, that
The solutions are (𝒂𝟐 + 𝒃𝟐 + 𝒄𝟐 + 𝒅𝟐 )(𝒙𝟐 + 𝒚𝟐 + 𝒛𝟐 𝒌𝟎 > 𝟏.
−𝟗 ± 𝟓 + 𝒘𝟐 ) Then there is a nontrivial solution
𝒙≡ (𝐦𝐨𝐝 𝟏𝟏). 𝒙𝟐 + 𝒚𝟐 + 𝒛𝟐 = 𝒌𝟎 𝒑.
𝟐 = (𝒂𝒙 − 𝒃𝒚 − 𝒄𝒛 − 𝒅𝒘)𝟐 + (𝒂𝒚
We need the inverse of + 𝒃𝒙 + 𝒄𝒘 − 𝒅𝒛)𝟐 Consider these values modulo 𝒌𝟎 .
𝟐 (𝐦𝐨𝐝 𝟏𝟏). By a geometric argument
+(𝒂𝒛 − 𝒃𝒘 + 𝒄𝒙 + 𝒅𝒚)𝟐
Since (originally used by Lagrange),
+ (𝒂𝒘 + 𝒃𝒛 − 𝒄𝒚
𝟐 ⋅ 𝟔 = 𝟏𝟐 ≡ 𝟏 (𝐦𝐨𝐝 𝟏𝟏), one shows that there exists a
+ 𝒅𝒙)𝟐 .
the inverse of 𝟐 is 𝟔. smaller multiple
This identity shows a crucial fact: 𝟐 𝟐 𝟐
First solution 𝒙 + 𝒚 + 𝒛 = 𝒌𝟏 𝒑
The product of two numbers,
−𝟗 + 𝟓 −𝟒 with
𝒙≡ = each a sum of four squares, is
𝟐 𝟐 again a sum of four squares. 𝟎 < 𝒌 𝟏 < 𝒌𝟎 .
≡ (−𝟒) This contradicts the minimality of
Thus the set of numbers
⋅ 𝟔 (𝐦𝐨𝐝 𝟏𝟏). 𝒌𝟎 .
representable as four squares is
Compute: Hence
closed under multiplication.
−𝟒 ⋅ 𝟔 = −𝟐𝟒 ≡ −𝟐𝟒 + 𝟑𝟑 𝒌𝟎 = 𝟏.
2. Show that every residue class
= 𝟗 (𝐦𝐨𝐝 𝟏𝟏). mod 𝒑 is a sum of three squares So we now have
So first solution: 𝒑 = 𝒙 𝟐 + 𝒚𝟐 + 𝒛𝟐 .
Consider all ordered triples
𝒙 ≡ 𝟗 (𝐦𝐨𝐝 𝟏𝟏). 5. Convert “three squares” into
(𝒙, 𝒚, 𝒛) with 𝟎 ≤ 𝒙, 𝒚, 𝒛 < 𝒑.
Second solution “four squares”
There are 𝒑𝟑 such triples.
−𝟗 − 𝟓 −𝟏𝟒 If a number is already a sum of
𝒙≡ = Form the expression
𝟐 𝟐 𝒙𝟐 + 𝒚𝟐 + 𝒛𝟐 (𝐦𝐨𝐝 𝒑). three squares, it is automatically
≡ (−𝟏𝟒) a sum of four squares by writing
Because there are only 𝒑 possible
⋅ 𝟔 (𝐦𝐨𝐝 𝟏𝟏). 𝒑 = 𝒙 𝟐 + 𝒚𝟐 + 𝒛 𝟐 + 𝟎𝟐 .
Reduce −𝟏𝟒 (𝐦𝐨𝐝 𝟏𝟏): residues but 𝒑𝟑 triples, by the
pigeonhole principle, at least one Let
−𝟏𝟒 ≡ −𝟏𝟒 + 𝟐𝟐 = 𝟖. 𝒂 = 𝒙, 𝒃 = 𝒚, 𝒄 = 𝒛, 𝒅 = 𝟎.
Thus residue 𝒓 satisfies:
Thus
𝟖 ⋅ 𝟔 = 𝟒𝟖 ≡ 𝟒 (𝐦𝐨𝐝 𝟏𝟏). 𝒙𝟐𝟏 + 𝒚𝟐𝟏 + 𝒛𝟐𝟏 ≡ 𝒙𝟐𝟐 + 𝒚𝟐𝟐
𝒑 = 𝒂𝟐 + 𝒃𝟐 + 𝒄𝟐 + 𝒅𝟐 .
So second solution: + 𝒛𝟐𝟐 (𝐦𝐨𝐝 𝒑),
This completes the proof.
𝒙 ≡ 𝟒 (𝐦𝐨𝐝 𝟏𝟏). with
Final Conclusion
Final Answer (𝒙𝟏 , 𝒚𝟏 , 𝒛𝟏 ) ≠ (𝒙𝟐 , 𝒚𝟐 , 𝒛𝟐 ).
Every prime number 𝒑 can
The solutions to Subtracting gives
indeed be expressed as the sum of
𝟐
𝟑𝒙 + 𝟓𝒙 + 𝟗 ≡ 𝟎 (𝐦𝐨𝐝 𝟏𝟏) 𝒙𝟐 + 𝒚𝟐 + 𝒛𝟐 ≡ 𝟎 (𝐦𝐨𝐝 𝒑), four squares:
are where
𝒑 = 𝒂𝟐 + 𝒃𝟐 + 𝒄𝟐 + 𝒅𝟐 .
𝒙 ≡ 𝟒 (𝐦𝐨𝐝 𝟏𝟏) , 𝒙 ≡ 𝟗 (𝐦𝐨𝐝 𝟏𝟏) . 𝒙 = 𝒙𝟏 − 𝒙𝟐 , 𝒚 = 𝒚𝟏 − 𝒚𝟐 , 𝒛
= 𝒛𝟏 − 𝒛𝟐 .
This is a direct application of the √𝑫 = [𝒂𝟎 ; 𝒂𝟏 , 𝒂𝟐 , … , 𝒂𝒌 ].
structure of quadratic forms and Let the convergents be Ques 12: Show that the
the minimality argument behind 𝒑𝒏
Lagrange’s Theorem. 𝒒𝒏
. Diophantine equation
Ques 11 ) What are A classical estimate for 𝒙 𝒚 + 𝒚 𝒚 𝒛 𝟐 = 𝟏has no
convergents says: solution in positive
Pell’s Equations? Derive 𝒑𝒏 𝟏
them. √𝑫 −
𝒒𝒏
< 𝟐.
𝒒𝒏
integers 𝒙, 𝒚, 𝒛.
Solution = solution = We present a long,
Multiply both sides by 𝒒𝟐𝒏 :
A Pell’s equation is a Diophantine clear, and rigorous justification
𝒑𝟐𝒏 − 𝑫𝒒𝟐𝒏 < 𝟏. that the equation cannot hold for
equation of the form
Since the left side is an integer, any positive integers. The key
𝒙𝟐 − 𝑫𝒚𝟐 = 𝟏,
the only possibility is idea is that the structure of the
where
𝒑𝟐𝒏 − 𝑫𝒒𝟐𝒏 = ±𝟏. left-hand side forces it to be at
 𝑫 is a positive integer,
Thus, the convergents to √𝑫 least 2, while the right-hand side
 𝑫 is not a perfect square,
automatically satisfy Pell’s is 1. No amount of substitution
 𝒙 and 𝒚 are required to be
equation. can escape this contradiction.
integers.
This is the rigorous derivation: Step 1. Consider the equation
This equation is fundamental in
Pell’s equation arises because the 𝒙 𝒚 + 𝒚 𝒚 𝒛 𝟐 = 𝟏.
number theory and arises
best rational approximations to A Diophantine equation asks for
naturally when studying
irrational numbers of the form √𝑫 satisfy this quadratic integer solutions, and in this case
Diophantine relation. we are restricted to positive
√𝑫. Pell’s equation always has 3. Algebraic Derivation Using integers, meaning
infinitely many integer solutions.
Norms 𝒙 ≥ 𝟏, 𝒚 ≥ 𝟏, 𝒛 ≥ 𝟏.
Below we derive Pell’s equation
Consider the quadratic field Step 2. Now examine each term
and explain why this special form
ℚ(√𝑫). on the left-hand side separately.
occurs.
Elements look like First, the term 𝒙 𝒚 . Since 𝒙is a
1. Begin with Approximating √𝑫 positive integer, the smallest value
For non-square 𝑫, the number 𝒙 + 𝒚√𝑫.
Define the norm: it can take is 1. Also, since 𝒚is a
√𝑫 is irrational. positive integer, the smallest
We look for rational 𝑵(𝒙 + 𝒚√𝑫) = (𝒙 + 𝒚√𝑫)(𝒙
exponent we can raise 𝒙to is 1.
approximations − 𝒚√𝑫)
Therefore, the smallest possible
𝒙 = 𝒙𝟐 − 𝑫𝒚𝟐 .
≈ √𝑫. value of 𝒙 𝒚 among positive
𝒚 If we require
integers occurs when 𝒙 = 𝟏and
Rewriting: 𝑵(𝒙 + 𝒚√𝑫) = 𝟏, 𝒚 = 𝟏, giving
𝒙 ≈ 𝒚√𝑫. we immediately obtain 𝒙 𝒚 = 𝟏𝟏 = 𝟏.
Square both sides: 𝒙𝟐 − 𝑫𝒚𝟐 = 𝟏. Thus, no matter what positive
𝒙𝟐 ≈ 𝑫𝒚𝟐 . Thus Pell’s equation is the integers 𝒙and 𝒚are, we always
Since 𝒙𝟐 and 𝑫𝒚𝟐 are integers, equation describing units in the have
the closest equality we can hope ring of integers of ℚ(√𝑫). 𝒙 𝒚 ≥ 𝟏.
for is 4. Final Definition and Meaning Step 3. Next consider the second
𝒙𝟐 − 𝑫𝒚𝟐 = ±𝟏. Therefore, Pell’s equation is: term 𝒚 𝒚 𝒛 𝟐 .
The form = 𝟏 is called Pell’s 𝒙𝟐 − 𝑫𝒚𝟐 = 𝟏, Since 𝒚is a positive integer, the
equation, and = −𝟏 is called the where 𝑫 is a positive non-square expression 𝒚 𝒚 is also a positive
negative Pell’s equation. integer. integer. Its smallest value occurs
Thus Pell’s equation comes It arises naturally from when 𝒚 = 𝟏, giving
directly from best rational  approximations to √𝑫, 𝒚 𝒚 = 𝟏𝟏 = 𝟏.
approximations of √𝑫.  continued fractions, Similarly, the term 𝒛𝟐 is a positive
2. Derivation Using Continued  algebraic number theory integer because 𝒛is positive. Its
Fractions (norm equation). smallest possible value occurs
Every irrational number √𝑫 has And it has infinitely many integer when 𝒛 = 𝟏, giving
a periodic continued fraction solutions, all generated from the 𝒛𝟐 = 𝟏.
expansion: smallest “fundamental solution”.
Therefore, the minimum possible (25) The value of Jacobi symbol
value of the product 𝒚 𝒚 𝒛 𝟐 is (22 / 102) is 1 = False
𝟏 ⋅ 𝟏 = 𝟏. (26) x² + 1 ≡ 0 (mod p) has a
Thus we always have solution = True
𝒚 𝒚 𝒛 𝟐 ≥ 𝟏. (1) There are finitely many (27) Real number with periodic
Step 4. Now add these two primes of the form 4k+2 = False infinite continued fraction is
inequalities: (2) There are infinitely many quadratic irrational = True
𝒙 𝒚 + 𝒚 𝒚 𝒛 𝟐 ≥ 𝟏 + 𝟏 = 𝟐. Fermat primes = False (28) If a|bc and (a,c)=1 then a|b =
Step 5. But the given equation (3) 341 is the least pseudoprime True
claims that this sum equals 1. So number = True (29) 111³³³ + 333¹¹¹ is divisible by 7
the equation demands (4) φ(9000) = 3600 and φ(100) = = True
𝒙 𝒚 + 𝒚 𝒚 𝒛 𝟐 = 𝟏. 40 = True (30) σ and τ are multiplicative =
This creates an immediate (5) If (a, b) = 1 then (b - a, a) = 1 = True
contradiction, because a sum of True
two positive integers can never be (6) If a ≡ b (mod p) then a² ≡ b² .
1. Even the absolute smallest CREATED BY ADITYA
(mod p), p prime = True
configuration gives the sum (7) The number π is algebraic =
𝟏 + 𝟏 = 𝟐.
NOTE; PLEASE USE IT
False
Hence the left-hand side is always (8) The remainder is unique when FOR YOUR STUDY
at least 2, never 1. a is divided by b = True AND PREPARE WELL
Step 6. Since the left-hand side (9) If a divides bc & (a, b) = 1 FOR EXAMS . WE
cannot possibly equal the right- then a divides c = True STRICTLY PROHIBIT
hand side under the restriction of (10) φ(n) is an additive function =
positive integers, the only logical False ANY ILLEGAL USE . IF
conclusion is that no positive (11) There are infinitely many YOU MISUSE IT FOR
integer solution can exist. primes of the type 4k+3 = True ILLEGAL PURPOSE.
Step 7. Therefore, the (12) If gcd(a,b)=d then gcd(a/d , YOU WILL BE
Diophantine equation b/d) = 1 = True
𝒙 𝒚 + 𝒚 𝒚𝒛 𝟐 = 𝟏 (13) The Pell equation is x² - d y²
RESPONSIBLE FOR IT ,
is unsatisfiable in the domain of = 1 = True NOT MAKERS
positive integers. No choice of (14) The arithmetic functions τ
positive integers for 𝒙, 𝒚,or 𝒛can and σ are multiplicative = True INSTA ID :
make the left-hand side as small (15) Möbius inversion formula Kiyotaka_adi_01
as 1. given is correct = True
This completes the long and (16) The value of Jacobi symbol उपयोग अपनी पढ़ाई और
detailed proof that the equation (22 / 105) is 1 = False
has no positive integer solution.
परी ाओं की अ ी
(17) x² + 1 ≡ 0 (mod p) has a
solution = True तैयारी के िलए कर। हम
(18) A real number with periodic िकसी भी गैरकानूनी
continued fraction is quadratic
irrational = True
उपयोग की स मना
(19) 111³³³ + 333¹¹¹ is divisible by 7 करते ह। अगर आप
= True इसका गलत इ ेमाल
(20) 18x + 15y = 48 is a solvable
Diophantine equation = True
करते ह, तो इसके िलए
(21) There are infinitely many आप िज़ ेदार होंगे, हम
primes of the type 4k+1 = True
(22) If gcd(a,b)=d then gcd(a/d , नह ं |
b/d) = 1 = True
(23) There are infinitely many
Mersenne primes = False
(24) φ(200) = 80 and φ(100) = 40 =
True