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!

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Problem N1:

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{aligned} 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{aligned}

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 - 7 years, 5 months ago

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

We claim the answer is no.

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$

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{aligned} 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{aligned}$ 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$

Awesome! Really nice job

Eddie The Head - 7 years, 5 months ago

Excellent!!

Kishan k - 7 years, 5 months ago

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 - 7 years, 5 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$