MATH 470 Lecture 4

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

Motivation and Math History

How to calculate $2^{17}(\mathrm{mod}7)$?

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

Order

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

For example,

• the order of 2 in $\mathbb{\mathbb{Z}}/7\mathbb{\mathbb{Z}}$ is 3: $2^3\equiv 1(\mathrm{mod}7)$
• the order of 1 in $\mathbb{\mathbb{Z}}/7\mathbb{\mathbb{Z}}$ is 1: $1^1\equiv 1(\mathrm{mod}7)$
• the order of 5 in $\mathbb{\mathbb{Z}}/7\mathbb{\mathbb{Z}}$ is 6: $5^6\equiv 1(\mathrm{mod}7)$

Fermat's Little Theorem

(See Fermat's Little Theorem→)

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

$x^p\equiv x(\mathrm{mod}p)$

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

$x^{p-1}\equiv 1(\mathrm{mod}p)$

Note: $p-1$ may not be the smallest integer $k$ for $x^k\equiv 1(\mathrm{mod}p)$.

• $2^6\equiv 1(\mathrm{mod}7)$
• $2^3\equiv 1(\mathrm{mod}7)$

Proof

Why is $x^{p-1}\equiv 1(\mathrm{mod}p)$ when $p\nmid x$?

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

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

• none are 0
• No two are the same. (suppose not, then $ix\equiv jx(\mathrm{mod}p)⟹(i-j)\mid p$ — contradiction)
• therefore, each will map uniquely to modulo classes

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

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=qk+r$

and

$0<r<k$

, then

$x^r\equiv (\mathrm{mod}p)$

— contradiction.

Q.E.D.

We know:

• $k$ is order in $x^k\equiv 1(\mathrm{mod}p)$
• $x^{p-1}\equiv 1(\mathrm{mod}p)$

Corollary 2

If $d$ and $e$ are integers such that $de\equiv 1(\mathrm{mod}p-1)$ and $p\nmid x$, then $x^{de}\equiv x(\mathrm{mod}p)$.

Proof. Rewrite $de\equiv 1(\mathrm{mod}p-1)$ as $de=q(p-1)+1$.

$x^{de}=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(\mathrm{mod}p)$

Corollary 3

If $\mathrm{G}\mathrm{C}\mathrm{D}(d,p-1)=1$, then the function $f:\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}\to \mathbb{\mathbb{Z}}/p\mathbb{\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(\mathrm{mod}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(\mathrm{mod}29)\to M$

How to break coding scheme ($x\mapsto x^3(\mathrm{mod}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 $de\equiv 1(\mathrm{mod}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(\mathrm{mod}10)$? YES

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

Examples:

• $n=5$: ${(\mathbb{\mathbb{Z}}/5\mathbb{\mathbb{Z}})}^{*}=\{1,2,3,4\}$
• $n=6$: ${(\mathbb{\mathbb{Z}}/6\mathbb{\mathbb{Z}})}^{*}=\{1,5\}$
• $n=9$: ${(\mathbb{\mathbb{Z}}/9\mathbb{\mathbb{Z}})}^{*}=\{1,2,4,5,7,8\}$
• $n=12$: ${(\mathbb{\mathbb{Z}}/12\mathbb{\mathbb{Z}})}^{*}=\{1,5,7,11\}$

Euler's Totient Function

Let $\varphi (n)=\text{number of integers in}{(\mathbb{\mathbb{Z}}/n\mathbb{\mathbb{Z}})}^{*}$

From previous examples,

• $\varphi (5)=4$
• $\varphi (6)=2$
• $\varphi (9)=6$
• $\varphi (12)=4$

In particular, $\varphi (p)=p-1$

Computation

How to compute $\varphi (n)$?

Basic fact: $\varphi (p)=p-1$

$\varphi (p^n)=p^n-p^{n-1}=p^{n-1}(p-1)$

since there are $p^{n-1}$ multiples of $p$ between 0 and $p^n$.

Properties: $\varphi (mn)=\varphi (m)\varphi (n)$

Take the product of the totients of the prime factorization of the number

Example

$100=2^2\cdot 5^2$

$\varphi (100)=\varphi (2^2)\varphi (5^2)=(2^2-2^1)(5^2-5^1)$

Euler's Theorem

For any integers $n$, $x$ such thta $\mathrm{G}\mathrm{C}\mathrm{D}(x,n)=1$,

$x^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

Example

What are the last two digits of $3^{4081}$? ($3^{4081}\equiv ◻(\mathrm{mod}100)$)

Let $n=100$, then $\varphi (100)=40$.

Therefore $3^{4081}=(3^{40}{)}^{◻}\cdot 3^1\equiv 3(\mathrm{mod}100)$

And the last two digits are "03"