Skip to main content

Section 5.4 A Number Trick

Let's start with another fun number game!

Exploration 5.4.1.

Pick a secret \(x\text{,}\) then compute \(y=x^5\) mod \(23\text{.}\) Now take \(y\) and compute \(z=y^{9} \pmod{23}\text{.}\) There is Sage code to help.

What happened? Why?


Examine \((x^5)^{9}=x^{45}\pmod{23}\) for all \(x\) mod 23. What do you notice?

Definition 5.4.1.

In general, we define a number trick to mean that we can find a \(d\) and \(e\) such that

\begin{equation*} (x^d)^e \equiv x \mod n \end{equation*}

for all \(x \bmod n\text{.}\)

In order for such a \(d\) and \(e\) to exist we need to know if we can find an \(a>1\) such that \(x^a \equiv x \pmod{n}\text{.}\) In fact, we want to know all possible values of \(a>1\) that will work.