mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2016-11-10, 23:10   #1
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

5×353 Posts
Default Basic Number Theory 8: equiv. relations and Fermat's little theorem

We have been looking at Euler's phi function.
For any positive integer \(n\), \(\phi(n)\) is defined as the number of units in the integers modulo \(n\), and we saw (in proposition 32) that this is also the number of integers in the range 0 to \(n-1\) inclusive that are coprime to \(n\). For any coprime positive integers \(m\) and \(n\), we also proved that \(\phi(mn)=\phi(m)\phi(n)\) (proposition 33).

Example
What is \(\phi(25)?\)
The positive divisors of 25 are 1, 5 and \(25=5^2\) so, for any integer \(a\), we have \(\gcd(a,25)=1\) if and only if \(a\) is not divisible by 5.
Consider the integers from 0 to 24 inclusive:
Code:
  0  1  2  3  4 
  5  6  7  8  9
 10 11 12 13 14
 15 16 17 18 19
 20 21 22 23 24
The entries in this table that are divisible by 5 are precisely the 5 entries in the first column, so \(\phi(25)=25-5=20\).
Let us do this more generally.

Proposition 34
Let \(p\) be a prime number and \(n\) a positive integer.
Then \(\phi(p^n)=(p-1)p^{n-1}\).

proof
Let \(S=\{0,1,2,\ldots,p^n-1\}\) and \(T=\{a\in S:\gcd(a,p^n)>1\}\).
Then \(\phi(n)=\#S-\#T\) by proposition 32.
As \(p\) is a prime number, the positive divisors of \(p^n\) are \(1,p,p^2,p^3,\ldots,p^n\) (and no others).
So, for each \(a\in S\), \(\gcd(a,p^n)>1\) if and only if \(p|a\).
Thus \(T=\{0,p,2p,3p,\ldots,p^n-p\}\) and therefore \(\#T=p^{n-1}\).
Hence \(\phi(n)=\#S-\#T=p^n-p^{n-1}=(p-1)p^{n-1}\). ∎

Using propositions 33 and 34 together, we can find \(\phi(n)\) for any positive integer \(n\) small enough to be factorized into its product of prime numbers.
The easy way to think of it is that you decrement one occurrence of each prime factor.
For example, \(\phi(2\cdot 2\cdot 2\cdot 5\cdot 5\cdot 11)=1\cdot 2\cdot 2\cdot 4\cdot 5\cdot 10\), i.e. \(\phi(2200)=800\).

Before we can go further with Number Theory, we need 2 more general mathematical concepts: partitions and equivalence relations.

Let \(S\) be a set. A partition of \(S\) is a collection of non-empty subsets of \(S\) such that each element of \(S\) occurs in precisely one of the subsets.

Example
For any positive integer \(m\), the \(m\) subsets
\[\begin{eqnarray*}
\bar{0} & = & \{mn:n\in\mathbb{Z}\} \\
\bar{1} & = & \{1+mn:n\in\mathbb{Z}\} \\
\bar{2} & = & \{2+mn:n\in\mathbb{Z}\} \\
\vdots \\
\overline{m-1} & = & \{(m-1)+mn:n\in\mathbb{Z}\}
\end{eqnarray*}\]
form a partition of \(\mathbb{Z}\).

We have already seen several examples of relations.
  • ">" is a relation on \(\mathbb{R}\): for any real numbers \(x,y\), "\(x>y\)" is a statement that is true or false.
  • "|" (i.e. "divides") is a relation on \(\mathbb{Z}\): for any integers \(a,b\), "\(a|b\)" is a statement that is true or false.
  • "\(\subset\)" is a relation on any set of sets: for any sets \(A,B\), "\(A\subset B\)" is a statement that is true or false.
  • Let \(n\) be a positive integer. Then \(\equiv\pmod{n}\) is a relation on \(\mathbb{Z}\): for any integers \(a,b\), "\(a\equiv b\pmod{n}\)" is either true or false.
  • "+" is not a relation: for any numbers \(x,y\), \(x+y\) is a number, not a statement.
(Technically, a relation on a set \(A\) is determined by the set of all ordered pairs of elements of \(A\) that are related in that way, so we define a relation on \(A\) as a subset of the Cartesian product \(A\times A\).
Similarly, for any sets \(A\) and \(B\), a relation from \(A\) to \(B\) is a subset of the Cartesian product \(A\times B\). Functions can also be defined in terms of relations. But understanding the idea here is more important than the technical definition.)

Notation
We may draw a line through any relation symbol to say that the relation does not hold.
For example, \(x\neq y\) means \(x\) is not equal to \(y\), and \(A\not\subset B\) means \(A\) is not a subset of \(B\).
We may write a relation symbol backwards for the reverse relation.
For example, \(y<x\) means \(x>y\), and \(B\supset A\) means \(A\subset B\). (This does not work if the symbol itself is symmetric!)
Also, we may use several relations in a row to assert that they all hold.
For example, \(x<y<z\) means \(x<y\) and \(y<z\), while \(a\in A\subset B\) means \(a\in A\) and \(A\subset B\).

Let \(A\) be a set and \(\sim\) a relation on \(A\).
We call the relation \(\sim\) reflexive if it has the following property:
for all \(x\in A\), we have \(x\sim x\).
We call the relation \(\sim\) symmetric if if has this property:
for all \(x,y\in A\), if \(x\sim y\) then \(y\sim x\).
And we call the relation \(\sim\) transitive if the following holds:
for all \(x,y,z\in A\), if \(x\sim y\) and \(y\sim z\) then \(x\sim z\).
We call \(\sim\) an equivalence relation on \(A\) if it is reflexive, symmetric and transitive.

Examples
The relation ">" on \(\mathbb{R}\) is not reflexive or symmetric but is transitive: for any real numbers \(x,y,z\), if \(x>y\) and \(y>z\) then \(x>z\).
The relation "|" on \(\mathbb{Z}\) is reflexive (since, for all integers \(n\) we have \(n|n\)) and transitive (exercise 5) but it is not symmetric.
For all positive integers \(n\), the relation \(\equiv\pmod{n}\) is reflexive, symmetric and transitive, and hence an equivalence relation on \(\mathbb{Z}\).

Notation
Let \(\sim\) be an equivalence relation on a set \(A\).
For each \(a\in A\), we write \([a]=\{x\in A:x\sim a\}\) and call this subset of \(A\) the equivalence class of \(a\) (under \(\sim\)).
We call the element \(a\) a representative of its equivalence class.
(Any element of an equivalence class may be chosen to represent it.)

Proposition 35
Let \(A\) be a set and \(\sim\) an equivalence relation on \(A\).
Then the equivalence classes under \(\sim\) form a partition of \(A\).

proof
The relation \(\sim\) is reflexive so, for all \(a\in A\) we have \(a\in [a]\).
Thus each equivalence class is a non-empty subset of \(A\), and every element of \(A\) is present in at least one equivalence class.
Take any \(a,b\in A\) and suppose that \([a]\cap [b]\neq\emptyset\), i.e. there exists an element \(c\) which is present in both \([a]\) and \([b]\).
Then \(c\sim a\) and \(c\sim b\).
As \(\sim\) is symmetric, we also have \(a\sim c\), and \(\sim\) is transitive too, so from \(a\sim c\) and \(c\sim b\) it follows that \(a\sim b\).
We now prove that \([a]=[b]\).
Take any \(x\in [a]\).
Then \(x\sim a\) and \(a\sim b\) and \(\sim\) is transitive so \(x\sim b\) and therefore \(x\in [b]\). Thus \([a]\subset [b]\).
Conversely, take any \(x\in [b]\).
Then \(x\sim b\) and \(b\sim a\) (since \(a\sim b\) and \(\sim\) is symmetric) so \(x\sim a\) (as \(\sim\) is transitive) hence \(x\in [a]\).
Thus \([b]\subset [a]\) as well, so \([a]\) and \([b]\) have precisely the same elements, making them equal.
We have shown that if two equivalence classes overlap then they are equal. It follows that each element of \(A\) is present in only 1 equivalence class.
This completes the proof that the equivalence classes form a partition of \(A\). ∎

We can now return to Number Theory.

For any numbers \(x,y\), if \(x\neq 0\) and \(y\neq 0\) but \(xy=0\) then we call \(x\) and \(y\) zero divisors. (Some people also count 0 as a zero divisor.)

In \(\mathbb{Z}\), there are no zero divisors (unless you count 0).
In the integers modulo 10, for example we have \(\bar{4}\times\bar{5}=\bar{0}\) so \(\bar{4}\) and \(\bar{5}\) are both zero divisors.
It follows that if \(\bar{5}x=\bar{5}y\) we cannot conclude that \(x=y\) (e.g. we could have \(x=\bar{3}\) and \(y=\bar{7}\)).
This problem does not occur with units. For example, \(\bar{3}\) is a unit in the integers modulo 10 with inverse \(\bar{7}\) so if \(\bar{3}x=\bar{3}y\) then \(x=\bar{7}\cdot\bar{3}x=\bar{7}\cdot\bar{3}y=y\).
In particular, if \(z\) is also an inverse for \(\bar{3}\) then \(\bar{3}z=\bar{1}=\bar{3}\cdot\bar{7}\) so it follows that \(z=\bar{7}\).
Thus the inverse of a unit is indeed unique, and we are justified in writing \(\bar{7}=\bar{3}^{-1}\).
For units, the usual laws of indices then extend to negative powers, i.e. if \(a\) and \(b\) are units then, for all integers \(m,n\), we have \(a^{m+n}=a^m\cdot a^n\), \(a^{mn}=(a^m)^n\) and \((ab)^n=a^nb^n\).
(You can easily prove these by induction if you wish.)

Proposition 36
Let \(m\) be a positive integer and \(a\in(\mathbb{Z}/m\mathbb{Z})^*\) (i.e. \(a\) is a unit in the integers modulo \(m\)).
Then \(a^n=\bar{1}\) for some positive integer \(n\).

proof
As \(a\) is a unit, there exists \(b\in\mathbb{Z}/m\mathbb{Z}\) such that \(ab=\bar{1}\).
There are only \(m\) distinct integers modulo \(m\), so the values \(\bar{1},a,a^2,a^3,\ldots,a^m\) cannot all be different.
Thus there exist non-negative integers \(i,j\) such that \(i>j\) but \(a^i=a^j\).
Let \(n=i-j\). Then \(n>0\) and \(a^n=a^ib^j=a^jb^j=1\). ∎

The smallest positive integer \(n\) for which \(a^n=\bar{1}\) is called the order of \(a\) in the unit group of the integers modulo \(m\).

Example
In the integers modulo 9, \(\bar{4}\) is a unit since \(\bar{4}\times\bar{7}=\bar{1}\).
We have \(\bar{4}\neq\bar{1}\), \(\bar{4}^2\neq\bar{1}\) but \(\bar{4}^3=\bar{1}\), so we say \(\bar{4}\) has order 3 in the unit group of integers modulo 9.
It follows that
\[ \ldots,\bar{4}^{-3}=\bar{1},\bar{4}^{-2}=\bar{4},\bar{4}^{-1}=\bar{7},
\bar{4}^0=\bar{1},\bar{4}^1=\bar{4},\bar{4}^2=\bar{7},
\bar{4}^3=\bar{1},\bar{4}^4=\bar{4},\bar{4}^5=\bar{7},
\bar{4}^6=\bar{1},\ldots \]

Proposition 37
Let \(m\) be a positive integer and \(a\in (\mathbb{Z}/m\mathbb{Z})^*\).
Let \(n\) be the order of \(a\) in this unit group.
Then \(\bar{1},a,a^2,a^3,\ldots,a^{n-1}\) are all distinct elements of \((\mathbb{Z}/m\mathbb{Z})^*\) and, for all integers \(k\), \(a^k=\bar{1}\) if and only if \(n|k\).

proof
As \(a\) is a unit, there exists \(b\in\mathbb{Z}/m\mathbb{Z}\) such that \(ab=\bar{1}\).
Suppose there exist integers \(i,j\in\{0,1,2,\ldots,n-1\}\) such that \(i>j\) but \(a^i=a^j\).
Then \(0<i-j<n\) but \(a^{i-j}=a^ib^j=a^jb^j=\bar{1}\) so \(n\) is not the smallest positive power of \(a\) equal to \(\bar{1}\), a CONTRADICTION.
Hence \(\bar{1},a,a^2,\ldots,a^{n-1}\) are all distinct in \(\mathbb{Z}/m\mathbb{Z}\).
Take any integer \(k\).
By proposition 5, there exist unique integers \(q\) and \(r\) such that \(k=qn+r\) and \(0\leq r<n\) (division with remainder).
If \(n|k\) then \(r=0\) and \(a^k=(a^n)^q=\bar{1}^q=\bar{1}\).
If \(n\) does not divide \(k\) then \(0<r<n\) and \(a^k=a^{qn+r}=(a^n)^qa^r=\bar{1}\cdot a^r\neq \bar{1}\) since \(\bar{1},a,a^2,\ldots,a^{n-1}\) are all distinct in \(\mathbb{Z}/m\mathbb{Z}\). ∎

Theorem 38
Let \(m\) be a positive integer, \(a\in (\mathbb{Z}/m\mathbb{Z})^*\) and \(n\in\mathbb{Z}\) the order of \(a\).
Define a relation \(\sim\) on the unit group \((\mathbb{Z}/m\mathbb{Z})^*\) as follows: \(x\sim y\) if and only if \(y^{-1}x=a^k\) for some integer \(k\).
Then \(\sim\) is an equivalence relation on \((\mathbb{Z}/m\mathbb{Z})^*\) and every equivalence class has precisely \(n\) distinct elements.

proof
Take any \(x,y,z\in\mathbb{Z}/m\mathbb{Z}\).
Then \(x^{-1}x=1=a^0\) so \(x\sim x\).
If \(x\sim y\) then \(y^{-1}x=a^k\) for some integer \(k\) so \(x^{-1}y=a^{-k}\) and therefore \(y\sim x\).
And if \(x\sim y\sim z\) then \(y^{-1}x=a^r\) and \(z^{-1}y=a^s\) for some integers \(r,s\) so \(z^{-1}x=z^{-1}yy^{-1}x=a^{s+r}\) hence \(x\sim z\).
Thus \(\sim\) is an equivalence relation on \((\mathbb{Z}/m\mathbb{Z})^*\).
Take any unit \(b\in(\mathbb{Z}/m\mathbb{Z})^*\).
For all integers \(k\), \(b^{-1}(ba^k)=a^k\) so \(ba^k\sim b\) and therefore \(ba^k\in [b]\).
Conversely, for any unit \(c\) if \(c\in [b]\) then \(c\sim b\) so \(b^{-1}c=a^k\) for some integer \(k\) and therefore \(c=ba^k\).
Thus \([b]=\{ba^k:k\in\mathbb{Z}\}\).
Take any integers \(r,s\). If \(a^r=a^s\) then \(ba^r=ba^s\).
Conversely, if \(ba^r=ba^s\) then (since \(b\) is a unit with an inverse \(b^{-1}\) in the integers modulo \(m\)), \(b^{-1}ba^r=b^{-1}ba^s\), i.e. \(a^r=a^s\).
By proposition 37, it follows that \(\#[b]=n\). ∎

Corollary 39
Let \(m\) be a positive integer, \(a\in (\mathbb{Z}/m\mathbb{Z})^*\) and \(n\in\mathbb{Z}\) the order of \(a\).
Then \(n|\phi(m)\).

proof
Under the equivalence relation defined in theorem 38, each equivalence class has precisely \(n\) elements. And the equivalence classes form a partition of \((\mathbb{Z}/m\mathbb{Z})^*\) by proposition 35, so \(n\) divides the number of elements in \((\mathbb{Z}/m\mathbb{Z})^*)\), which is \(\phi(n)\) (by definition). ∎

Corollary 40
Let \(m\) be a positive integer and \(a\) an integer with \(\gcd(a,m)=1\).
Then \(a^{\phi(m)}\equiv 1\pmod{m}\).

proof
As \(\gcd(a,m)=1\), we have \(\bar{a}\in(\mathbb{Z}/m\mathbb{Z})^*\) by proposition 32. Let \(n\) be the order of \(\bar{a}\).
By corollary 39, \(n|\phi(m)\) so, by proposition 37, \(\bar{a}^{\phi(m)}=\bar{1}\), i.e. \(a^{\phi(m)}\equiv 1\pmod{m}\). ∎

In particular, if \(p\) is a prime number then \(\phi(p)=p-1\) by proposition 34
so, for any integer \(a\) not divisible by \(p\), \(a^{p-1}\equiv 1\pmod{p}\).

Corollary 41 (Fermat's little theorem)
For all prime numbers \(p\) and all integers \(a\),
\(a^p\equiv a\pmod{p}\).

proof
If \(p|a\) then \(a\equiv 0\pmod{p}\) and the result follows immediately.
Otherwise, \(a^{p-1}\equiv 1\pmod{p}\) by corollary 40, so \(a^p\equiv a\pmod{p}\). ∎

Exercises
36. Let \(m,n\) be positive integers and \(a\) a unit of order \(n\) in the integers modulo \(m\). Show that \(a^{-1}\) also has order \(n\).
37. Calculate \(11^{345^{678}}\bmod{13}\) without using a computer.
38. Let \(p\) be a prime number greater than 2 and suppose there exists \(x\) in the integers modulo \(p\) such that \(x^2+\bar{1}=\bar{0}\).
Prove that \(p\bmod{4}=1\).
39. (RSA) Let \(p,q\) be distinct prime numbers, \(n=pq\) and \(e,d\) non-negative integers less than \((p-1)(q-1)\) such that \(\bar{e}\) is a unit with inverse \(\bar{d}\) in the integers modulo \((p-1)(q-1)\).
Show that, for any non-negative integer \(m\) with \(m<n\), we have \(m^{ed}\bmod{n}=m\).

Last fiddled with by Nick on 2016-12-14 at 09:50 Reason: Variable typo in statement of Corollary 41 (replaced m with p).
Nick is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 1 & 2 Nick Number Theory Discussion Group 17 2017-12-23 20:10
Basic Number Theory 20: polynomials Nick Number Theory Discussion Group 5 2017-04-25 14:32
Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic Nick Number Theory Discussion Group 0 2017-01-07 13:15
Basic Number Theory 14: a first look at groups Nick Number Theory Discussion Group 0 2016-12-29 13:47
Basic Number Theory 6: functions and the Chinese Remainder Theorem Nick Number Theory Discussion Group 4 2016-10-31 22:26

All times are UTC. The time now is 15:57.


Tue Nov 29 15:57:52 UTC 2022 up 103 days, 13:26, 1 user, load averages: 0.85, 0.72, 0.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔