## 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\).

*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}\)