Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 10D / b

Table of contents
- Solution b

Solution

The Fermat-Euler theorem gives

a^{φ (N)} \equiv 1 (mod N),

so the multiplicative order

r = ord_{N} (a)

exists. For every integer

k

,

f (k + r) = a^{k + r} \equiv a^{k} a^{r} \equiv a^{k} = f (k) (mod N) .

Thus the modular exponential is periodic with period

r

. If

t > 0

were a smaller period, then

f (t) = f (0)

would give

a^{t} \equiv 1 (mod N)

, contradicting the minimality of

r

. Hence

r

is its least positive period.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version