Modulo Arithmetic
Problems
- Divisibility tests
- Difference of squares
- Fermat’s little theorem
- Chinese remainder theorem
- Is a square?
- Pigeon-hole principle
- Pigeon-hole on pairs
- Perfect square in a sequence
Divisibility tests
A2, 2021
If \(p\) is a prime number, which of the following are true?
(a) For every prime \(p\), \(p^2-p\) is divisible by 3.
(b) For every prime \(p>3\), exactly \(p-1\) or \(p+1\) is divisible by 6.
(c) For every prime \(p>3\), \(p^2-1\) is divisible by 24.
(d) For every prime \(p>3\), one of \(p+1\),\(p+3\) and \(p+5\) is divisible by 8.
Solution
(a) False. \(5^2-5\) is not divisible by 3.
(b) True. Both 3 and 2 must be factors of either \(p-1\) or \(p+1\). Since \(p\) is an odd prime, it is not divisible by 3. So either \(p-1\) or \(p+1\) is divisible by 3. But \(p-1\) and \(p+1\) are both even.
(c) True. \(p\) is either \(4k+1\) or \(4k+3\). So \(p^2-1\) has 8 and 3 as factors.
(d) False. Put \(p=17\).
Difference of squares
A5, 2018
List in increasing order all positive integers \(n \leq 40\) such that \(n\) cannot be written in the form \(a^{2}-b^{2},\) where \(a\) and \(b\) are positive integers.
Solution
1,4 and all even number s of the form \(4 k+2\).
Fermat’s little theorem
A5, 2010
Find the remainder given by \(3^{89} \times 7^{86}\) when divided by 17.
Solution
The usual trick is to try to get numbers that are 1,-1 modulo the divisor. In this case, \(16\equiv -1 \mod 17\). We cannot get 16 directly but notice that \( 21 \equiv 4 \mod 17 \), which we can get.
\(3^{89} 7^{86} \equiv 3^{3}(3 \cdot 7)^{86} \equiv 27 \cdot 4^{86} \equiv 10\left(4^{2}\right)^{43} \equiv 10(-1)^{43} \equiv-10 \equiv 7\)
Chinese remainder theorem
A10, 2020
Find positive integers \(a,b,c\leq 475\) such that:
\begin{align} a\equiv 0\pmod {25} & \quad a\equiv 1\pmod {19} \\ \\ b\equiv 1\pmod {25} & \quad b\equiv 0\pmod {19} \\ \\ c\equiv 10\pmod{25} & \quad c\equiv 4\pmod {19} \end{align}
Solution
Background: Chinese remainder theorem (CRT)
We want to find a \(p\) such that: \begin{align} p \equiv p_{1} &\: \left(\bmod\; n_{1}\right) \\ p \equiv p_{2} &\: \left(\bmod\; n_{2}\right) \end{align} where \(n_{1}\) and \(n_{2}\) are coprime. Bezout's theorem proves the existence of two integers \(m_{1}\) and \(m_{2}\) such that: \[ m_{1} n_{1}+m_{2} n_{2}=1 \] The integers \(m_{1}\) and \(m_{2}\) can be found by the extended Euclidean algorithm. A solution is given by \[ p=p_{1} m_{2} n_{2}+p_{2} m_{1} n_{1} \] Further, the solution is unique modulo \(n_1n_2\).
Is a square?
A6, 2019
For what values of \( n \) is \( n^6 + n^4 + 1 \) a square of a natural number?
Solution
We will handle odd and even cases separately.
Lemma. Every odd square is \(1 \bmod 8\).
\[ (2k+1)^2=4k^2+4k+1=4(k^2+k)+1 \] Since \( 4(k^2+k) \) is divisible by 8, the lemma follows. \(\square\)Case 1. If \(n\) is odd, then the given expression \(S:=n^6+n^4+1\) cannot be a square since \(S\equiv 3\pmod 8\). Hence \(n\) is not odd.
Case 2. If \(n=2\), we have \(S=81\), so we have one solution. If \(n>2\) and is even we have:
\[ \left(n^3+\frac{n}{2}\right)^2=n^6+n^4+\frac{n^2}{4}> S > n^6+n^4-2n^3+\frac{n^2}{4}-n+1=\left(n^3+\frac{n}{2}-1\right)^2 \]
\( S \) is a number strictly inbetween two consecutive squares, so there are no solutions for \(n>2\).
Pigeon-hole principle
B1, 2010
Let \(a_{1}, a_{2}, \ldots, a_{100}\) be 100 positive integers. Show that for some \(m, n\) with \(1 \leq m \leq n \leq\) \(100, \sum_{i=m}^{n} a_{i}\) is divisible by 100.
Solution
Consider the remainders of the sequence when divided by 100. If some \(a_k\bmod100=0\), then \(m=n=k\) will work. Otherwise, the reminders are between 1 and 99 for every number.
Since there are 100 numbers, there must be two indices \(i\) and \(j\) such that \(a_i\bmod 100=a_j\bmod 100\). Pick \(m=i\) and \(n=j\), if \( i < j \).
Similar problem. Prove that there exists a number consisting of only 1s and 0s that is divisible by 3.
Pigeon-hole on pairs
B7, 2012
A sequence of integers \(c_{n}\) starts with \(c_{0}=0\) and satisfies \(c_{n+2}=a c_{n+1}+b c_{n}\) for \(n \geq 0,\) where \(a\) and \(b\) are integers. For any positive integer \(k\) with \(g c d(k, b)=1,\) show that \(c_{n}\) is divisible by \(k\) for infinitely many \(n\)
Solution
Let \( r_i = c_i \mod k \). We want to prove that the sequence of \(r_i\)s has infinitely many zeroes.
Lemma. For all \(i> 0\), \(r_i\) and \(r_{i+1}\) uniquely determine \(r_{i-1}\).
Proof. Since \(k\) and \(b\) are co-prime, \(b\) has an inverse modulo \(k\). That is, there is a unique number \(b^{-1}\) such that \( bb^{-1} = 1\).
\begin{align} b^{-1}r_{n+2}&=b^{-1}ar_{n+1}+bb^{-1}r_{n} \\ r_{n} &= b^{-1}(ar_{n+1} - r_{n+2}) \quad\quad\square \end{align}
The lemma implies that there are infinite number of zeros in the sequence of \(r_i\)s. If not, we can find the last zero. Look at the infinite sequence starting from the last zero. Since there are only \(k^2\) distinct pairs, some pair must repeat by pigeon-hole principle. Let \(ab\) be the first pair of consecutive numbers that repeats. Let \(x\) and \(y\) be the numbers that come before the first and the second instance of the pair. Due to the above lemma, given the pair \(ab\), the previous number is unique. So \(x=y\). But this violates our assumption that \(ab\) is the first pair that repeats.
Perfect square in a sequence
B4, 2017
The domain of a function \(f\) is the set of natural numbers. The function is defined as follows:
\[ f(n)=n+\lfloor\sqrt{n}\rfloor \]
where \(\lfloor k\rfloor\) denotes the smallest integer less than or equal to \(k .\) For example, \(\lfloor\pi\rfloor=\) \(3,\lfloor 4\rfloor=4 .\) Prove that for every natural number \(m\) the following sequence contains at least one perfect square
\[ m, f(m), f^{2}(m), f^{3}(m), \ldots \]
The notation \(f^{k}\) denotes the function obtained by composing \(f\) with itself \(k\) times, e.g., \(f^{2}=f \circ f\)
Solution
If \(m\) is itself a square then we are done. So assume that \(m=k^{2}+j\) for \(1 \leq j \leq 2 k\). Hence we have \(f(m)=k^{2}+j+k\). Consider the following two sets:
\(A=\left\{m \text{ a natural number} \mid m=k^{2}+j \text { and } 0 \leq j \leq 2 k\right\} \)
\(B=\left\{m \text{ a natural number} \mid m=k^{2}+j \text { and } k+1 \leq j \leq 2 k\right\} \)
Suppose \(m\) is in the set \(B\). Then
\[ \begin{align} f(m) &=k^{2}+j+k \\ &=(k+1)^{2}+(j-k-1) \end{align} \]
Hence \(f(m)\) is eit her a square or is in \(A .\) Thus it is enough to assume that \(m \in A\) In that case \(k^{2}< f(m)< (k+1)^{2},\) so \(\lfloor f(m)\rfloor=k\). Therefore
\[ f^{2}(m)=(k+1)^{2}+(j-1) \]
This clearly implies that \(f^{2 j}(m)=(k+j)^{2}\)