Numbers and Sets | Part IA, 2008

(a) Let aa and mm be integers with 1a<m1 \leqslant a<m and let d=(a,m)d=(a, m) be their highest common factor. For any integer bb, prove that bb is a multiple of dd if and only if there exists an integer rr satisfying the equation arb(modm),andshowthatinthiscasetherearea r \equiv b \operatorname{(\operatorname {mod}m)\text {,andshowthatinthiscasethereare}} exactly dd solutions to the equation that are distinct modm\bmod m.

Deduce that the equation arb(modm)a r \equiv b(\bmod m) has a solution if and only if b(m/d)0b(m / d) \equiv 0 (modm)(\bmod m).

(b) Let pp be a prime and let Zp\mathbb{Z}_{p}^{*} be the multiplicative group of non-zero integers modp\bmod p. An element xx of Zp\mathbb{Z}_{p}^{*} is called a kk th power (modp)(\bmod p) if xyk(modp)x \equiv y^{k}(\bmod p) for some integer yy. It can be shown that Zp\mathbb{Z}_{p}^{*} has a generator: that is, an element uu such that every element of Zp\mathbb{Z}_{p}^{*} is a power of uu. Assuming this result, deduce that an element xx of Zp\mathbb{Z}_{p}^{*} is a kk th power (modp)(\bmod p) if and only if x(p1)/d1(modp)x^{(p-1) / d} \equiv 1(\bmod p), where dd is now the highest common factor of kk and p1p-1.

(c) How many 437th powers are there mod 1013? [You may assume that 1013 is a prime number.]

Typos? Please submit corrections to this page on GitHub.