MATH 470 Lecture 4

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

Motivation and Math History

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

1. 4^th grade . . .
2. 8^th grade: k = [0..]; remainders = repeat [1, 2, 4]; $2^{17}{\pmod {7}}=4$ by the pattern (when does it repeat?)
3. 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}}$
4. Even faster! (secret: $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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d = 3} and $p=29$, we need to find $d\,e\equiv 1{\pmod {28}}$: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e = 19}

Generalization

What about when we replace $p$ by any integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1, 2, \ldots, n-1 \}} with $\mathrm {GCD} (k,n)=1$.

Examples:

• $n=5$: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \mathbb{Z} / 5 \mathbb{Z} \right)^* = \{ 1,2,3,4 \}}
• $n=6$: $\left(\mathbb {Z} /6\mathbb {Z} \right)^{*}=\{1,5\}$
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 9} : $\left(\mathbb {Z} /9\mathbb {Z} \right)^{*}=\{1,2,4,5,7,8\}$
• $n=12$: $\left(\mathbb {Z} /12\mathbb {Z} \right)^{*}=\{1,5,7,11\}$

Euler's Totient Function

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

From previous examples,

• $\phi (5)=4$
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(6) = 2}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(9) = 6}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(12) = 4}

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

Computation

How to compute $\phi (n)$?

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

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

since there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^{n-1}} multiples of $p$ between 0 and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^n} .

Properties: $\phi (m\,n)=\phi (m)\,\phi (n)$

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

Example

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 100 = 2^2 \cdot 5^2}

$\phi (100)=\phi (2^{2})\,\phi (5^{2})=(2^{2}-2^{1})\,(5^{2}-5^{1})$

Euler's Theorem

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

$x^{\phi (n)}\equiv 1{\pmod {n}}$

Example

What are the last two digits of $3^{4081}$? (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3^{4081} \equiv \Box \pmod{100}} )

Let $n=100$, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(100) = 40} .

Therefore Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3^{4081} = (3^{40})^\Box \cdot 3^1 \equiv 3 \pmod{100}}

And the last two digits are "03"