Waste less time on Facebook — follow Brilliant.

Topics in Number Theory: Some problems involving congruence relations (Part I)

For this note I assume that you know the basics properties of divisibility including those of the congruence relation \(a\equiv b \pmod{c}\). See for example Modular arithmetics

I will show some nice problems involving the congruence relation, most of them are very useful in problem solving, thus we can consider this problems as lemmas.

Problem 1. If \(\gcd(a,n)=1\) then there exists an integer \(b\) such that \(ab \equiv 1 \pmod{n}\). \(b\) is called the multiplicative inverse of \(a\) modulo \(n\).

Solution. Consider the numbers \(a\cdot 1, a\cdot 2, a\cdot 3, \ldots, a\cdot n\). If \(a\cdot i\equiv a\cdot j \pmod{n}\) for \(1\leq i,j\leq n\), then \(a\cdot(i-j)\equiv 0\pmod{n}\), since \(\gcd(a,n)=1\) we conclude that \((i-j)\equiv 0 \pmod{n}\) and then \(i=j\). Thus the numbers \(a\cdot 1, a\cdot 2, a\cdot 3, \ldots, a\cdot n\) are pairwise distinct modulo \(n\), since this set consists of \(n\) numbers then it is a complete residue system modulo \(n\). In particular, for some \(1\leq b\leq n\) we have \(a\cdot b\equiv 1\pmod{n}\).

Problem 2. Let \(n>1\) be an integer:

  • If \(n\) is prime then \((n-1)!\equiv -1 \pmod{n}\). [Wilson's Theorem]

  • If \(n\) is composite and \(n\neq 4\) then \((n-1)!\equiv 0 \pmod{n}\).

Hint for the first part. If \(n\geq 2\) is an odd prime, prove that the set \(\{2, 3, \ldots, n-2\}\) can be divided in pairs \(\{a,a'\}\) where \(a\) and \(a'\) are inverse each other.

Problem 3. If \(p\) is a prime and \(1\leq k<p\) then \({p \choose k}\equiv 0 \pmod{p}\).

Solution. We know that \({p \choose k}=\frac{p!}{k!(p-k)!}\) then \({p \choose k}\cdot k!\cdot (p-k)!=p!\). The number \(p!\) is divisible by \(p\) while \(k!\cdot (p-k)!\) is not, then \({p \choose k}\) is divisible by \(p\).

Problem 4. If \(p\) is a prime then \((a+b)^p\equiv a^p+b^p \pmod{p}\).

Hint. Use the previous problem.

Now, you can practice with the following problems. To avoid confusion I will call these problems N1, N2, etc.

Problem N1. ¿Does there exist a positive integer \(n\) for wich the set \(\{n, n+1, \ldots, n+17\}\) can be partitioned in two subsets \(\mathcal{A}\) and \(\mathcal{B}\) such that the product of the elements of \(\mathcal{A}\) is equal to the product of the elements of \(\mathcal{B}\)?

Problem N2. Let \(p\geq3\) be a prime. For each \(i = 1, 2, \ldots, p-1\) denote by \(r_i\) the remainder when \(i^p\) is divided by \(p^2\), thus \(0\leq r_i<p^2\). Calculate \(r_1+r_2+\cdots+r_{p-1}\).

Please post your comments and solutions!

Note by Jorge Tipe
3 years, 9 months ago

No vote yet
1 vote


Sort by:

Top Newest

Problem N1:

We claim the answer is no.

Lemma: No element in the set can be a multiple of 19.

Proof: Assume that an element in the set is divisible by 19. Then, since the set is composed of 18 consecutive integers, there can be no other element in the set that is divisible by 19. However, then the product of the elements in the two sets cannot be equal, as one has a factor of 19, while the other doesn't, a contradiction. \(\square\)

Since the set is composed of 18 consecutive integers, none of which is divisible by 19, the set must be equivalent to the set \(\{1,2,\cdots,18\}\) when reduced modulo 19. If this set can be partitioned into two subsets with the same product, the product of the elements must be a square. By Wilson's theorem, the product of the elements is congruent to \(-1\) modulo 19. However, it is well-known that \(-1\) is a quadratic residue modulo an odd prime \(p\) if and only if that prime is \(1\) modulo 4. Since \(19\equiv 3\pmod 4\), we conclude that no such integer \(n\) exists. \(\blacksquare\)

Problem N2:

We claim the answer is \(\dfrac{p^2(p-1)}{2}\).

Lemma: \(i^p+(p-i)^p\equiv 0\pmod{p^2}\), and \(r_i+r_{p-i}=p^2\).

Proof: By the binomial theorem, \[\begin{align} i^p+(p-i)^p&\equiv i^p+p^p-\dbinom{p}{1}p^{p-1}i+\cdots-\dbinom{p}{p-2}p^2i^{p-2}+\dbinom{p}{p-1}pi^{p-1}-i^p\pmod{p^2} \\ &\equiv i^p+0-0+\cdots-0+\dbinom{p}{p-1}pi^{p-1}-i^p\pmod{p^2} \\ &\equiv i^p+p^2i^{p-1}-i^p\pmod{p^2} \\ &\equiv 0\pmod{p^2} \end{align}\] However, also note that, for \(1\le i\le p-1\), \(p^2\nmid i^p\). Since \(0<r_i<p^2\), \(0<r_{p-i}<p^2\), and \(r_i+r_{p-i}\equiv 0\pmod{p^2}\), we must have that \(r_i+r_{p-i}=p^2\), as desired. \(\square\)

By the lemma, and since \(p-1\) is even, the set of integers \(r_1,r_2,\cdots,r_{p-1}\) can be paired, \(r_i\) with \(r_{p-i}\), such that the sum of each pair is \(p^2\). The total number of pairs is \(\dfrac{p-1}{2}\), and so we conclude \(r_1+r_2+\cdots+r_{p-1}=\dfrac{p^2(p-1)}{2}\). \(\blacksquare\) Daniel Chiu · 3 years, 9 months ago

Log in to reply

@Daniel Chiu Awesome! Really nice job Eddie The Head · 3 years, 8 months ago

Log in to reply

Since Problem 4 has no proof, I will write one, though the hint really gives it away..

By the binomial theorem we have that, \((a + b)^p = \sum\limits^p_{k=0} \binom{p}{k} a^k b^{p - k}\)

By Problem 3, we know that \(1 \leq k < p \Rightarrow \binom{p}{k} \equiv 0 \pmod p\), and so all of the summands except for the first and last ones are zeroed. We are then left with,

\((a + b)^p \equiv \binom{p}{0} a^p + \binom{p}{p} b^p \equiv a^p + b^p \pmod p\ \quad \square\) Ben Frankel · 3 years, 9 months ago

Log in to reply

Excellent!! Kishan K · 3 years, 9 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...