MATH 470 Lecture 4

« previous | Thursday, January 24, 2013 | next »

Motivation and Math History

How to calculate $2^{17}{\pmod {7}}$ ?

4^th grade . . .
8^th grade: k = [0..]; remainders = repeat [1, 2, 4]; $2^{17}{\pmod {7}}=4$ by the pattern (when does it repeat?)
College:
- $2^{1}\equiv 2{\pmod {7}}$
- $2^{2}\equiv 4{\pmod {7}}$
- $2^{4}\equiv 2{\pmod {7}}$
- $2^{8}\equiv 2{\pmod {7}}$
- $2^{16}\equiv 4{\pmod {7}}$
- $2^{32}\equiv 2{\pmod {7}}$
- $2^{17}\equiv 2^{16}\cdot 2^{1}\equiv 2\cdot 2\equiv 4{\pmod {7}}$
Even faster! (secret: $2^{6}\equiv 1{\pmod {7}}$ $2^{6}\equiv 1{\pmod {7}}$ )
- $2^{17}=2^{6\cdot 2+5}\equiv {\cancel {2^{6}}}\cdot {\cancel {2^{6}}}\cdot 2^{5}\equiv 4{\pmod {7}}$
- How to find in general for mod $n$ ?

Order

Definition: For any prime $p$ , $\forall x\in \mathbb {Z}$ and $p\nmid x$ , the order of $x$ in $\mathbb {Z} /p\mathbb {Z}$ is the minimum positive integer $k$ such that $x^{k}\equiv 1{\pmod {p}}$ .

For example,

the order of 2 in $\mathbb {Z} /7\mathbb {Z}$ is 3: $2^{3}\equiv 1{\pmod {7}}$
the order of 1 in $\mathbb {Z} /7\mathbb {Z}$ is 1: $1^{1}\equiv 1{\pmod {7}}$
the order of 5 in $\mathbb {Z} /7\mathbb {Z}$ is 6: $5^{6}\equiv 1{\pmod {7}}$

Fermat's Little Theorem

(See Fermat's Little Theorem→)

Given any prime $p$ and any integer $x$ ,

x^{p}\equiv x{\pmod {p}}

This is often written as $p\nmid x$ , then

x^{p-1}\equiv 1{\pmod {p}}

Note:

p-1

may not be the smallest integer

k

for

x^{k}\equiv 1{\pmod {p}}

.

$2^{6}\equiv 1{\pmod {7}}$
$2^{3}\equiv 1{\pmod {7}}$

Proof

Why is $x^{p-1}\equiv 1{\pmod {p}}$ when $p\nmid x$ ?

Define modulo classes $1,2,\ldots ,p-1$ .

Multiply by $x$ : $x,2x,\ldots ,(p-1)x$ .

none are 0
No two are the same. (suppose not, then $i\,x\equiv j\,x{\pmod {p}}\implies (i-j)\mid p$ — contradiction)
therefore, each will map uniquely to modulo classes

Take prouct of each group: ${\begin{aligned}\prod _{i=1}^{p-1}i&\equiv \prod _{i=1}^{p-1}x{\pmod {p}}\\(p-1)!&\equiv (p-1)!x{\pmod {p}}\\1\equiv x{\pmod {p}}\end{aligned}}$

We can divide by $(p-1)!$ since it is not a multiple of $p$ .

Q.E.D.

Corollary 1

For any $x$ such that $p\nmid x$ , the order of $x$ is a factor of $p-1$ . Why?

Proof. If $p-1=q\,k+r$ and $0<r<k$ , then $x^{r}\equiv {\pmod {p}}$ — contradiction.

Q.E.D.

We know:

$k$ is order in $x^{k}\equiv 1{\pmod {p}}$
$x^{p-1}\equiv 1{\pmod {p}}$

Corollary 2

If $d$ and $e$ are integers such that $d\,e\equiv 1{\pmod {p-1}}$ and $p\nmid x$ , then $x^{d\,e}\equiv x{\pmod {p}}$ .

Proof. Rewrite $d\,e\equiv 1{\pmod {p-1}}$ as $d\,e=q(p-1)+1$ .

$x^{d\,e}=x^{q(p-1)+1}$

By Fermat's little theorem, $x^{q(p-1)+1}\equiv \left(x^{p-1}\right)^{2}\,x\equiv x{\pmod {p}}$

Corollary 3

If $\mathrm {GCD} (d,p-1)=1$ , then the function $f:\mathbb {Z} /p\mathbb {Z} \to \mathbb {Z} /p\mathbb {Z}$ defined by $f(x)=x^{d}$ has inverse $g(x)=x^{e}$ .

Application Example

Written on board at beginning of class:

plaintext:  ITWASABOUTELEVENOCLOCKINTHEMORNING
ciphertext: MISGXGZFDILULOLGFEUFEPMJICLQFNJMJR

The code was build by $p=29$ with function $f(x)=x^{3}{\pmod {29}}$ .

Correspondence

A B C D . . .  Z
2 3 4 5       27

We omit 0 and 1 since $\{0,1\}^{3}=\{0,1\}$ . That's not very secure.

For example, we take the first letter 'I' with correspondence 10:

$I\to 10\to 1000\equiv 14{\pmod {29}}\to M$

How to break coding scheme ( $x\mapsto x^{3}{\pmod {29}}$ ), we need to find "cubic root" mod 29.

Corollary 2 and 3 tell us that for $d=3$ and $p=29$ , we need to find $d\,e\equiv 1{\pmod {28}}$ : $e=19$

Generalization

What about when we replace $p$ by any integer $n$ ?

For example, "What is the last digit of

3^{17}

?" is another way of asking "3^{17} \equiv \Box \pmod{10}"

Can we find a number $k$ such that $3^{k}\equiv 1{\pmod {10}}$ ? YES

For any integer $n$ , we define $\left(\mathbb {Z} /n\mathbb {Z} \right)^{*}$ to be the set of all integers $k$ in $\{1,2,\ldots ,n-1\}$ with $\mathrm {GCD} (k,n)=1$ .