Prove that for any prime \(p\) there exist \(a\) and \(b\) in \(mathbb{Z}/p\mathbb{Z}\) such that \(a^2+b^2 \equiv -1\) modulo \(p\).
For prime number \(p=4t+1\) the equation \(s^2\equiv -1\) has two distinct solutions in \(\{1,2,...,p-1\}\), for the prime \(p=2\) there is only one solution, for \(p=4t+3\) there are no solutions.
Prove that any prime \(p=4t+1\) can be represented as a sum of two squares.
Gaussian numbers: The numbers of the form \(a+bi\) where both \(a\) and \(b\) are integer and \(i^2=-1\) are called Gaussian numbers and are denoted as \(\mathbb{Z}[i]\). Gaussian numbers contain \(0\) and \(1\), can be added, and multiplied, which makes them a ring. Describe all Gaussian numbers which have a multiplicative inverse in \(\mathbb{Z}[i]\), i.e. all those you can divide by.
Euclidean rings: we call a ring "Euclidean" if division with a remainder is possible in the ring. In integer numbers we can divide \(a\) by \(b\) with a remainder if there exist unique \(r\) and \(q\) such that \(r <b\) and \(a=bq+r\), now for Gaussian numbers we need to define what does "\(<\)" mean and what does "unique".
Prove that the division with remainder using the complex norm \(|x+yi| = (x+yi)(x-yi)\) is well defined. Namely for any \(a\) and \(b\) there exist unique (up to multiplicatively invertible element) Gaussian numbers \(q\) and \(r\) with \(|r| <|b|\).
As a corollary (you don’t have to prove but you can use it in later problems) any Gaussian number has a unique (up to \(1,-1,i,-i\)) prime decomposition in \(\mathbb{Z}[i]\).
Find prime decomposition of \(2,3,5,7\) as Gaussian numbers.
A number with one hundred \(0\)s, one hundred \(1\)s, and one hundred \(2\)s is written on the board. Could this number be a perfect square? You may use the divisibility rules for \(3\) and \(9\): a number is divisible by \(3\) (respectively \(9\)) if the sum of its digits is divisible by \(3\) (respectively \(9\)).
How many divisors does the number \(3^{31}\times 5^{23}\times 7^5\) have?
Recall that \(n! = n\times (n-1)\times (n-2)\times \cdots\times 2\times 1\). Can \(n!\) end in exactly \(5\) zeroes for some \(n\)?