I gave this talk at CMI STEMS final camp 2024. Definitions Before proceeding, we must be clear about what our title means. What do you mean by Counting? What do we mean by the term counting? We are going to prove that Rational numbers are countable . That is, there is a bijection between natural numbers and rational numbers. A bijective function $f:X\rightarrow Y$ is a one-to-one (injective) and onto (surjective) mapping of a set $X$ to a set $Y$. Note that every bijection from set $X$ to a set $Y$ also has an inverse function from set $Y$ to set $X$. But how are we going to create the bijection? We will first create a bijection between the Natural numbers and Positive rationals. Let $f(1),f(2),\dots $ be the mapping from natural numbers from $\Bbb{N}\rightarrow +\Bbb{Q}$. Then, note that there is also a bijection from $\Bbb{N}\rightarrow -\Bbb{Q}$ by simply mapping $i\in \Bbb{N}\rightarrow -f(i)$. And to create the bijection from $g:\Bbb{N} \rightarrow \Bbb{Q}$, c
Theory We know what Fermat's little theorem states. If $p$ is a prime number, then for any integer $a$, the number $a^p − a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as \[a^{p}\equiv a{\pmod {p}}.\] So, essentially, for every $(a,m)=1$, ${a}^{\phi (m)}\equiv 1 \pmod {m}$. But $\phi (m)$ isn't necessarily the smallest exponent. For example, we know $4^{12}\equiv 1\mod 13$ but so is $4^6$. So, we care about the "smallest" exponent $d$ such that $a^d\equiv 1\mod m$ given $(a,m)=1$. Orders Given a prime $p$, the order of an integer $a$ modulo $p$, $p\nmid a$, is the smallest positive integer $d$, such that $a^d \equiv 1 \pmod p$. This is denoted $\text{ord}_p(a) = d$. If $p$ is a primes and $p\nmid a$, let $d$ be order of $a$ mod $p$. Then $a^n\equiv 1\pmod p\implies d|n$. Let $n=pd+r, r\ll d$. Which implies $a^r\equiv 1\pmod p.$ But $d$ is the smallest natural number. So $r=0$. So $d|n$. Show that $n$ divid