Euler function, DYK Fact #560
 JaneFairfax Posted: 15:30 Wednesday 01 April 2009 The Enlightenment Group: Moderators Posts: 673 Member No.: 20 Joined: 03 Mar 2007 Did you know? If for each positive integer n we let $\phi(n)$ denote the number of integers less than or equal to n and coprime with n, then $\phi\,:\,\mathbb{Z}^+\to\mathbb{Z}^+$ is called the Euler function. We have this interesting little result: $\sum_{d\mid n}\phi(d)\ =\ n$ The proof of this given in A Course in Number Theory by H.E. Rose is only a few lines long.
 Athene_noctua Posted: 16:53 Wednesday 01 April 2009 Beyond Infinity Group: Admin Posts: 2 202 Member No.: 2 Joined: 03 Jan 2007 Did you know? Leonhard Euler (1707–83) was a Swiss mathematician. -------------------- Athene noctua
 JaneFairfax Posted: 18:03 Wednesday 01 April 2009 The Enlightenment Group: Moderators Posts: 673 Member No.: 20 Joined: 03 Mar 2007 Did you know? If gcd(m,n) = 1, $\phi(mn)=\phi(m)\phi(n)$. This result can be proved by abstract algebra. In particular, if $\left(\mathbb{Z}/k\mathbb{Z}\right)^\times$ denotes the multiplicative group of congruence classes modulo k of integers coprime with k, then if gcd(m,n) = 1, $\left(\mathbb{Z}/mn\mathbb{Z}\right)^\times$ is isomorphic to $\left(\mathbb{Z}/m\mathbb{Z}\right)^\times\,\times\,\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$. In fact, $\mathbb{Z}/mn\mathbb{Z}$ and $\mathbb{Z}/m\mathbb{Z}\,\oplus\,\mathbb{Z}/n\mathbb{Z}$ are isomorphic as rings, and it can be proved from this that the multiplicative group of units modulo mn is isomorphic to the product of the multiplicative groups of units modulo m and modulo n.
 Athene_noctua Posted: 19:01 Wednesday 01 April 2009 Beyond Infinity Group: Admin Posts: 2 202 Member No.: 2 Joined: 03 Jan 2007 Did you know? Euler became blind in the latter part of his life. -------------------- Athene noctua
 JaneFairfax Posted: 19:37 Wednesday 01 April 2009 The Enlightenment Group: Moderators Posts: 673 Member No.: 20 Joined: 03 Mar 2007 Did you know? If gcd(a,n) = 1, $a^{\phi(n)}\equiv1\,\pmod{n}$. Proof: Let $c_1,\,\ldots\,,\,c_{\phi(n)}$ be $\phi(n)$ integers such that gcd(ci, n) = 1 and $c_i\,\not\equiv\,{c_j}\,\pmod{n}$ if i ≠ j. Then, since gcd(a,n) = 1, $ac_1,\,\ldots\,,\,ac_{\phi(n)}$ are also $\phi(n)$ integers such that gcd(aci, n) = 1 and $ac_i\,\not\equiv\,{ac_j}\,\pmod{n}$ if i ≠ j. Hence $\prod_{i\,=\,1}^{\phi(n)}ac_i\,\equiv\,\prod_{i\,=\,1}^{\phi(n)}c_i\,\pmod{n}$ – and the result follows as $\gcd\left(\prod_{i\,=\,1}^{\phi(n)}c_i,\,n\right)=1$.
 algebraic topology Posted: 14:04 Thursday 02 April 2009 Renaissance Group: Friends Posts: 143 Member No.: 14 Joined: 20 Feb 2007 Did you know? If p is a prime, φ(p) = p−1 and this becomes Fermat’s little theorem: ap−1 ≡ 1 (mod p) provided a is not a multiple of p.
 JaneFairfax Posted: 14:45 Thursday 02 April 2009 The Enlightenment Group: Moderators Posts: 673 Member No.: 20 Joined: 03 Mar 2007 Did you know? In the language of Galois theory, Fermat’s little theorem says that if p is prime, then $\mathbb{Z}/p\mathbb{Z}$ is a splitting field for the polynomial $x^{p-1}-1$ in $\mathbb{Z}/p\mathbb{Z}\,[x]$.
 algebraic topology Posted: 20:26 Thursday 02 April 2009 Renaissance Group: Friends Posts: 143 Member No.: 14 Joined: 20 Feb 2007 Did you know? That means $(x-1)(x-2)\cdots(x-[p-1])\equiv{x}^{p-1}-1\,\pmod{p}$ Letting x = 0 gives $(-1)^{p-1}(p-1)!\equiv-1\,\pmod{p}$. If p > 2, we have $(p-1)!\equiv-1\,\pmod{p}$; if p = 2, the same equation is true as $1\equiv-1\,\pmod2$. This proves Wilson’s theorem.
 JaneFairfax Posted: 05:50 Friday 03 April 2009 The Enlightenment Group: Moderators Posts: 673 Member No.: 20 Joined: 03 Mar 2007 Did you know? The converse of Wilson’s theorem is also true: if $(p-1)!\equiv-1\,\pmod{p}$ then p is a prime.
0 User(s) are reading this topic (0 Guests and 0 Anonymous Users)
0 Members:
Join the millions that use us for their forum communities. Create your own forum today.