Past exam of the mathematics course of the University of Cambridge / 2008 / ia / Paper 4 / 6D (Numbers and Sets)

Let $d=\gcd (a,m)$. If the linear congruence $ar\equiv b(\mathrm{mod}m)$ holds, then $b=ar-ms$ for some integer $s$, so the greatest common divisor $d$ divides $b$. Conversely, Bézout's identity gives integers $u,v$ with $au+mv=d$. If $b=dj$, multiply this identity by $j$ to obtain $a(uj)\equiv b(\mathrm{mod}m)$. HenceFor the number of solutions, write $a=d{a}^{\prime }$, $m=d{m}^{\prime }$ and $b=d{b}^{\prime }$. The linear congruence becomes $a^{\prime }r\equiv b^{\prime }(\mathrm{mod}{m}^{\prime })$, where $a^{\prime },m^{\prime }$ are coprime integers. Multiplication by $a^{\prime }$ is invertible modulo $m^{\prime }$ by Bézout's identity, so the solutions form one residue class $r\equiv r_0(\mathrm{mod}{m}^{\prime })$. Modulo $m=d{m}^{\prime }$, these are exactlyThey are distinct: if two have the same residue class modulo $m$, then $d{m}^{\prime }$ divides $(j-\ell )m^{\prime }$, forcing $d\mid j-\ell$; with $0\le j,\ell <d$, this forces $j=\ell$. Every other solution differs from $r_0$ by a multiple of $m^{\prime }$, so these exhaust the $d$ solutions.

Finally,Combining this with the existence criterion gives the requested equivalent modular congruence.

Take a generator $u$ of the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$, which has order $p-1$. Write $x=u^a$. Since any possible nonzero base is $y=u^r$, the condition of being a $k$th power isBy part (a), this linear congruence is soluble exactly when $d=\gcd (k,p-1)$ divides $a$. MeanwhileThus the required test isThe exponent residue classes divisible by $d$ are $0,d,\dots ,p-1-d$, so there are exactly $(p-1)/d$ distinct nonzero $k$th powers. Equivalently, part (a) shows each value has exactly $d$ preimages under the power map.

The greatest common divisor issince $19$ and $44$ are coprime integers. Part (b) therefore gives $\boxed{1012/23=44}$ distinct $437$th powers in the nonzero multiplicative group of a finite field ${\mathbb{F}}_{1013}^{\times }$. If “powers mod $1013$” includes all residue classes, the additional value $0=0^{437}$ gives $\boxed{45}$ values including zero. The distinction is relevant because part (b) explicitly works in the nonzero group.