Motivating Number Theory/Combinatorics questions leading to finite field

Question

I want to learn about Finite Field, but don't want to learn but by starting from the memorizing the axioms of finite field, I wanna learn it by solving a few problems (good if NT /Combinatorics), which statement doesn't involve finite fields, but from which the notion of finite field comes naturally, and then developing the idea by myself.

What are some good such examples of such problems ?

(Note that some people are wrongly interpreting the ASCII art given in bounty text. It's not what you think, its just a finger pointing upward that I found here)

Answer 1

Here is the question that in fact got me interested in finite fields:

How does the Fibonacci sequence behave $\bmod p$, for $p$ a prime?

In particular, here are two exercises. Suppose $p \neq 5$. Let $\left( \frac{5}{p} \right)$ denote the Legendre symbol, which, as it turns out, is equal to $1$ if $p \equiv 1, 4 \bmod 5$ and $-1$ if $p \equiv 2, 3 \bmod 5$.

Exercise 1: Show that $F_p \equiv \left( \frac{5}{p} \right) \bmod p$.

Exercise 2: Show that $F_{p - \left( \frac{5}{p} \right)} \equiv 0 \bmod p$.

Answer 2

The following problem is from Babai and Frankl's textbook on linear algebra methods in combinatorics. One of the motivating factors of fields in general is that they support all the operations needed to perform linear algebra, which means that we can apply the concepts of rank and linear independence to vectors over a finite field.

There is a town of $n$ people who form clubs (each club being just a set of townspeople) according to the following rules:

1. The number of members of any given club must be odd (i.e. every set has odd cardinality).
2. Given any two different clubs, the number of people they have in common must be even (i.e. intersections have even cardinality).

What is the maximum number of clubs that can be formed while conforming to these rules?

Answer 3

In my opinion, I found the unexpected application of finite field in the following problem about sum-free sets by Paul Erdös:

Theorem. (Erdös) A set of integers $B$ is call a sum-free set if for any $x,y \in B$ then $x+y \not\in B$. Prove that for any set of nonzero integers $A$, there is a sum-free subset $B \subseteq A$ of size $|B|>\frac 13 |A|$.

The theorem's statement has no connection to finite field. Surprisingly, the proof for this uses probabilistic method combining with working in $\mathbf{Z}_p$.