Prove that squares of natural numbers can only be \(0\) or \(1\) modulo \(4\). The corollary states that no number of the form \(4t+3\) can be represented as a sum of two squares.
For a prime number \(p\) denote by \(mathbb{Z}/p\mathbb{Z}\) the set of integers \(\{0,1,2,3...,p-1\}\) with addition and multiplication modulo \(p\). By this we mean that \(p-1+4\) add up to \(3\) modulo \(p\) and the product of two residues \(a\) and \(b\) is viewed as the residue of \(ab\) modulo \(p\). Note that the set of the elements of \(mathbb{Z}/p\mathbb{Z}\) contains \(0\) and every element has an additive inverse, namely for an element \(a\) there exists an element \(b = p-a\) in \(mathbb{Z}/p\mathbb{Z}\) such that \(a+b = 0\) modulo \(p\). Such a set with addition, multiplication, \(0\) and additive inverses is called a Ring.
For example For \(p=5\) we have \(mathbb{Z}/5\mathbb{Z}\) as the set: \(\{0,1,2,3,4\}\), where \(2+3 = 0\) so the additive inverse for \(2\) modulo \(5\) is \(3\), \(3+4= 2\), \(2\times 3 = 1\), \(3\times 4 = 2\).
Prove that for a prime number \(p\) the ring \(mathbb{Z}/p\mathbb{Z}\) contains a multiplicative inverse for any non zero element. Namely, for any \(a \neq 0\) modulo \(p\) there exists \(b\) modulo \(p\), such that \(ab = 1\) modulo \(p\). A ring with this property of multiplicative inverses is called a Field.
For a prime number \(p\) denote by \(\lfloor\frac{p}{2}\rfloor\) the element of \(mathbb{Z}/p\mathbb{Z}\), which corresponds to the largest integer which is smaller than \(\frac{p}{2}\). Prove that all the elements \(\{1, 2^2, 3^2, ..., \lfloor\frac{p}{2}\rfloor^2\}\) are different in \(mathbb{Z}/p\mathbb{Z}\).
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\)).