Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

šŸ“š The CoCalc Library - books, templates and other resources

133957 views
License: OTHER
Tweet
Share
Share
Kernel: 
%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section6.3Fermat's and Euler's Theorems

Ā¶

The $\phi$- is the map $\phi : {\mathbb N } \rightarrow {\mathbb N}$ defined by $\phi(n) = 1$ for $n=1\text{,}$ and, for $n \gt 1\text{,}$ $\phi(n)$ is the number of positive integers $m$ with $1 \leq m \lt n$ and $\gcd(m,n) = 1\text{.}$

From PropositionĀ 3.4, we know that the order of $U(n)\text{,}$ the group of units in ${\mathbb Z}_n\text{,}$ is $\phi(n)\text{.}$ For example, $|U(12)| = \phi(12) = 4$ since the numbers that are relatively prime to 12 are 1, 5, 7, and 11. For any prime $p\text{,}$ $\phi(p) = p-1\text{.}$ We state these results in the following theorem.

Theorem6.17

Let $U(n)$ be the group of units in ${\mathbb Z}_n\text{.}$ Then $|U(n)| = \phi(n)\text{.}$

The following theorem is an important result in number theory, due to Leonhard Euler.

Theorem6.18Euler's Theorem

Let $a$ and $n$ be integers such that $n \gt 0$ and $\gcd(a, n) = 1\text{.}$ Then $a^{\phi(n)} \equiv 1 \pmod{n}\text{.}$

Proof

By TheoremĀ 6.17 the order of $U(n)$ is $\phi(n)\text{.}$ Consequently, $a^{\phi(n)} = 1$ for all $a \in U(n)\text{;}$ or $a^{\phi(n)} - 1$ is divisible by $n\text{.}$ Therefore, $a^{\phi(n)} \equiv 1 \pmod{n}\text{.}$

If we consider the special case of Euler's Theorem in which $n = p$ is prime and recall that $\phi(p) = p - 1\text{,}$ we obtain the following result, due to Pierre de Fermat.

Theorem6.19Fermat's Little Theorem

Let $p$ be any prime number and suppose that $p \notdivide a$ ($p$ does not divide $a$). Then

\begin{equation*} a^{p-1} \equiv 1 \pmod{ p }. \end{equation*}

Furthermore, for any integer $b\text{,}$ $b^p \equiv b \pmod{ p}\text{.}$

SubsectionHistorical Note

Ā¶

Joseph-Louis Lagrange (1736ā€“1813), born in Turin, Italy, was of French and Italian descent. His talent for mathematics became apparent at an early age. Leonhard Euler recognized Lagrange's abilities when Lagrange, who was only 19, communicated to Euler some work that he had done in the calculus of variations. That year he was also named a professor at the Royal Artillery School in Turin. At the age of 23 he joined the Berlin Academy. Frederick the Great had written to Lagrange proclaiming that the ā€œgreatest king in Europeā€ should have the ā€œgreatest mathematician in Europeā€ at his court. For 20 years Lagrange held the position vacated by his mentor, Euler. His works include contributions to number theory, group theory, physics and mechanics, the calculus of variations, the theory of equations, and differential equations. Along with Laplace and Lavoisier, Lagrange was one of the people responsible for designing the metric system. During his life Lagrange profoundly influenced the development of mathematics, leaving much to the next generation of mathematicians in the form of examples and new problems to be solved.