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:

$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$.

Examples:

• $n=5$: $\left(\mathbb {Z} /5\mathbb {Z} \right)^{*}=\{1,2,3,4\}$
• $n=6$: $\left(\mathbb {Z} /6\mathbb {Z} \right)^{*}=\{1,5\}$
• $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$
• $\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, 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(p) = p-1}

Computation

How to compute $\phi (n)$?

Basic fact: 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(p) = p-1}

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(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 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} between 0 and $p^{n}$.

Properties: 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(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}

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) = \phi(2^2) \, \phi(5^2) = (2^2-2^1) \, (5^2-5^1)}

Euler's Theorem

For any 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 n} , $x$ such thta 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 \mathrm{GCD}(x,n) = 1} ,

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 x^{\phi(n)} \equiv 1 \pmod{n}}

Example

What are the last two digits of 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}} ? (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 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 = 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"