Euler totient function - Revision history

Vipul: /* Initial values */

2014-01-29T22:44:31Z

Initial values

← Older revision		Revision as of 22:44, 29 January 2014
Line 65:		Line 65:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! <math>n</math> !! Prime factorization !! Totient function <math>\varphi(n)</math> !! <math>n - \varphi(n)</math> (equals 1 iff <math>n</math> is prime) !! <math>\varphi(n)/n</math> (reduced, equals product of <math>(1 - 1/p)</math> for primes <math>p</math> dividing <math>n</math> -- depends only on the ''set'' of prime divisors) !! Universal exponent <math>\lambda(n)</math> !! <math>\varphi(n)/\lambda(n)		! <math>n</math> !! Prime factorization !! Totient function <math>\varphi(n)</math> !! <math>n - \varphi(n)</math> (equals 1 iff <math>n</math> is prime) !! <math>\varphi(n)/n</math> (reduced, equals product of <math>(1 - 1/p)</math> for primes <math>p</math> dividing <math>n</math> -- depends only on the ''set'' of prime divisors) !! Universal exponent <math>\lambda(n)</math> !! <math>\varphi(n)/\lambda(n)</math>
	\|-		\|-
	\| [[1]] \|\| empty \|\| 1 \|\| 0 \|\| 1 \|\| 1 \|\| 1		\| [[1]] \|\| empty \|\| 1 \|\| 0 \|\| 1 \|\| 1 \|\| 1
Line 91:		Line 91:
	\| Power <math>p^k</math>, <math>p</math> odd \|\| <math>p^k</math> \|\| <math>p^{k-1}(p-1)</math> \|\| <math>p^{k-1}</math> \|\| <math>1 - (1/p)</math> \|\| <math>p^{k-1}</math> \|\| 1		\| Power <math>p^k</math>, <math>p</math> odd \|\| <math>p^k</math> \|\| <math>p^{k-1}(p-1)</math> \|\| <math>p^{k-1}</math> \|\| <math>1 - (1/p)</math> \|\| <math>p^{k-1}</math> \|\| 1
	\|}		\|}

	==Related arithmetic functions==		==Related arithmetic functions==

Vipul: /* Related arithmetic functions */

2014-01-29T22:44:02Z

Related arithmetic functions

← Older revision		Revision as of 22:44, 29 January 2014
Line 62:		Line 62:
	\|}		\|}

			==Initial values==

			{\| class="sortable" border="1"
			! <math>n</math> !! Prime factorization !! Totient function <math>\varphi(n)</math> !! <math>n - \varphi(n)</math> (equals 1 iff <math>n</math> is prime) !! <math>\varphi(n)/n</math> (reduced, equals product of <math>(1 - 1/p)</math> for primes <math>p</math> dividing <math>n</math> -- depends only on the ''set'' of prime divisors) !! Universal exponent <math>\lambda(n)</math> !! <math>\varphi(n)/\lambda(n)
			\|-
			\| [[1]] \|\| empty \|\| 1 \|\| 0 \|\| 1 \|\| 1 \|\| 1
			\|-
			\| [[2]] \|\| 2 \|\| 1 \|\| 1 \|\| 1/2 \|\| 1 \|\| 1
			\|-
			\| [[3]] \|\| 3 \|\| 2 \|\| 1 \|\| 2/3 \|\| 2 \|\| 1
			\|-
			\| [[4]] \|\| <math>2^2</math> \|\| 2 \|\| 2 \|\| 1/2 \|\| 2 \|\| 1
			\|-
			\| [[5]] \|\| 5 \|\| 4 \|\| 1 \|\| 4/5 \|\| 4 \|\| 1
			\|-
			\| [[6]] \|\| <math>2 \cdot 3</math> \|\| 2 \|\| 4 \|\| 1/3 \|\| 2 \|\| 1
			\|-
			\| [[7]] \|\| 7 \|\| 6 \|\| 1 \|\| 6/7 \|\| 6 \|\| 1
			\|-
			\| [[8]] \|\| <math>2^3</math> \|\| 4 \|\| 4 \|\| 1/2 \|\| 2 \|\| 1
			\|-
			\| [[9]] \|\| <math>3^2</math> \|\| 6 \|\| 3 \|\| 2/3 \|\| 6 \|\| 1
			\|-
			\| Prime <math>p</math> \|\| <math>p</math> \|\| <math>p - 1</math> \|\| 1 \|\| <math>1 - (1/p)</math> \|\| <math>p - 1</math> \|\| 1
			\|-
			\| Power <math>2^k</math> \|\| <math>2^k</math> \|\| <math>2^{k-1}</math> \|\| <math>2^{k-1}</math> \|\| 1/2 \|\| <math>2^{k-2}</math> if <math>k \ge 3</math>, else <math>2^{k-1}</math> \|\| 2 if <math>k \ge 3</math>, 1 otherwise
			\|-
			\| Power <math>p^k</math>, <math>p</math> odd \|\| <math>p^k</math> \|\| <math>p^{k-1}(p-1)</math> \|\| <math>p^{k-1}</math> \|\| <math>1 - (1/p)</math> \|\| <math>p^{k-1}</math> \|\| 1
			\|}
	==Related arithmetic functions==		==Related arithmetic functions==

Vipul: /* Relations expressed in terms of Dirichlet products */

2014-01-29T22:34:34Z

Relations expressed in terms of Dirichlet products

← Older revision		Revision as of 22:34, 29 January 2014
Line 87:		Line 87:
	\| <math>\varphi * U = E</math>\|\| <math>U</math> \|\| the function that sends every natural number to 1 \|\| <math>E</math> \|\| the function that sends every natural number to itself \|\| <math>\sum_{d\|n} \varphi(d) = n</math> \|\| Direct combinatorial argument: each summand is the number of elements in <math>\{ 1, \dots, n \}</math> whose gcd with <math>n</math> with <math>n/d</math>. \|\| <math>\varphi = E * \mu</math>, where <math>\mu</math> is the [[Mobius function]]. This follows from the fact that <math>\mu = U^{-1}</math>.<br>Also, <math>\varphi * \sigma_1 = E * E</math>, follows from this and <math>\sigma_1 = E * U</math>.		\| <math>\varphi * U = E</math>\|\| <math>U</math> \|\| the function that sends every natural number to 1 \|\| <math>E</math> \|\| the function that sends every natural number to itself \|\| <math>\sum_{d\|n} \varphi(d) = n</math> \|\| Direct combinatorial argument: each summand is the number of elements in <math>\{ 1, \dots, n \}</math> whose gcd with <math>n</math> with <math>n/d</math>. \|\| <math>\varphi = E * \mu</math>, where <math>\mu</math> is the [[Mobius function]]. This follows from the fact that <math>\mu = U^{-1}</math>.<br>Also, <math>\varphi * \sigma_1 = E * E</math>, follows from this and <math>\sigma_1 = E * U</math>.
	\|-		\|-
	\| <math>\varphi * \sigma_0 = \sigma_1</math> \|\| <math>\sigma_0</math> \|\| the [[divisor count function]] \|\| <math>\sigma = \sigma_1</math> \|\| the [[divisor sum function]] \|\| <math>\sum_{d\|n} \varphi(d) \sigma_0(n/d) = \sigma(n)</math> \|\| ~~Proof:~~ We have <math>\sigma_0 = U * U</math> and <math>\sigma_1 = E * U</math> by definition. Multiply both sides of the former by <math>\varphi</math> and use associativity to get <math>\varphi * \sigma_0 = (\varphi * U) * U</math>. Use the preceding identity to get <math>\varphi * \sigma_0 = E * U</math>, so <math>\varphi * \sigma_0 = \sigma_1</math> \|\|		\| <math>\varphi * \sigma_0 = \sigma_1</math> \|\| <math>\sigma_0</math> \|\| the [[divisor count function]] \|\| <math>\sigma = \sigma_1</math> \|\| the [[divisor sum function]] \|\| <math>\sum_{d\|n} \varphi(d) \sigma_0(n/d) = \sigma(n)</math> \|\| We have <math>\sigma_0 = U * U</math> and <math>\sigma_1 = E * U</math> by definition. Multiply both sides of the former by <math>\varphi</math> and use associativity to get <math>\varphi * \sigma_0 = (\varphi * U) * U</math>. Use the preceding identity to get <math>\varphi * \sigma_0 = E * U</math>, so <math>\varphi * \sigma_0 = \sigma_1</math> \|\|
	\|}		\|}

Vipul: /* Relations expressed in terms of Dirichlet products */

2014-01-29T22:34:17Z

Relations expressed in terms of Dirichlet products

← Older revision		Revision as of 22:34, 29 January 2014
Line 83:		Line 83:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! Statement !! Function !! Value of the Dirichlet product <math>\varphi *</math> the function !! Description !! Statement in ordinary notation !! Proof !! Corollaries		! Statement !! Function !! Description !! Value of the Dirichlet product <math>\varphi *</math> the function !! Description !! Statement in ordinary notation !! Proof !! Corollaries
	\|-		\|-
	\| <math>\varphi * U = E</math>\|\| <math>U</math> \|\| the function that sends every natural number to 1 \|\| <math>E</math> \|\| the function that sends every natural number to itself \|\| <math>\sum_{d\|n} \varphi(d) = n</math> \|\| Direct combinatorial argument: each summand is the number of elements in <math>\{ 1, \dots, n \}</math> whose gcd with <math>n</math> with <math>n/d</math>. \|\| <math>\varphi = E * \mu</math>, where <math>\mu</math> is the [[Mobius function]]. This follows from the fact that <math>\mu = U^{-1}</math>.<br>Also, <math>\varphi * \sigma_1 = E * E</math>, follows from this and <math>\sigma_1 = E * U</math>.		\| <math>\varphi * U = E</math>\|\| <math>U</math> \|\| the function that sends every natural number to 1 \|\| <math>E</math> \|\| the function that sends every natural number to itself \|\| <math>\sum_{d\|n} \varphi(d) = n</math> \|\| Direct combinatorial argument: each summand is the number of elements in <math>\{ 1, \dots, n \}</math> whose gcd with <math>n</math> with <math>n/d</math>. \|\| <math>\varphi = E * \mu</math>, where <math>\mu</math> is the [[Mobius function]]. This follows from the fact that <math>\mu = U^{-1}</math>.<br>Also, <math>\varphi * \sigma_1 = E * E</math>, follows from this and <math>\sigma_1 = E * U</math>.

Vipul at 22:32, 29 January 2014

2014-01-29T22:32:51Z

@@ Line 33: / Line 33: @@
 | [[satisfies property::divisibility-preserving function]] || Yes || If <math>m</math> and <math>n</math> are natural numbers such that <math>m</math>divides <math>n</math>, then <math>\varphi(m)</math> divides <math>\varphi(n)</math>.
 |}
 ==Behavior==
@@ Line 130: / Line 137: @@
 This identity holds not just for the formal Dirichlet series, but also for their analytic continuations, and is valid universally for the meromorphic functions.

Vipul: /* Dirichlet series */

2014-01-29T22:31:42Z

Dirichlet series

← Older revision		Revision as of 22:31, 29 January 2014
Line 123:		Line 123:
	Using the [[Dirichlet product]] identity <math>\varphi * U = E</math> and the fact that [[Dirichlet series of Dirichlet product equals product of Dirichlet series]], we get:		Using the [[Dirichlet product]] identity <math>\varphi * U = E</math> and the fact that [[Dirichlet series of Dirichlet product equals product of Dirichlet series]], we get:

	<math>\sum_{n \in \mathbb{N}} \frac{\varphi(n)}{n^s} \sum_{n \in mathbb{N}} \frac{1}{n^s} = \sum_{n \in \mathbb{N}} \frac{n}{n^s}</math>.		<math>\sum_{n \in \mathbb{N}} \frac{\varphi(n)}{n^s} \sum_{n \in \mathbb{N}} \frac{1}{n^s} = \sum_{n \in \mathbb{N}} \frac{n}{n^s}</math>.

	This simplifies to:		This simplifies to:

Vipul: /* Inequalities */

2014-01-29T22:31:04Z

Inequalities

← Older revision		Revision as of 22:31, 29 January 2014
Line 101:		Line 101:
	! Nature of bound (upper bound or lower) !! Formula !! Arithmetic functions used !! Explanation !! Asymptotic implication		! Nature of bound (upper bound or lower) !! Formula !! Arithmetic functions used !! Explanation !! Asymptotic implication
	\|-		\|-
	\| lower \|\| <math>\pi(n) - \omega(n)</math>\|\| <math>\pi(n)</math> is the [[prime-counting function]], and counts the number of primes less than or equal to <math>n</math>, while <math>\omega(n)</math> is the [[prime divisor count function]] of <math>n</math>. \|\| Any prime less than or equal to <math>n</math> that does ''not'' divide <math>n</math> must be relatively prime to <math>n</math>. \|\| <math>\pi(n) \sim \frac{n}{\operatorname{Li}(n)}</math>, whereas <math>\omega(n) = O(\log n)</math>. Thus, we get an asymptotic lower bound of <math>~n/\operatorname{Li}(n)</math>.		\| lower \|\| <math>\pi(n) - \omega(n)</math>\|\| <math>\pi(n)</math> is the [[prime-counting function]], and counts the number of primes less than or equal to <math>n</math>, while <math>\omega(n)</math> is the [[prime divisor count function]] of <math>n</math>. \|\| Any prime less than or equal to <math>n</math> that does ''not'' divide <math>n</math> must be relatively prime to <math>n</math>. \|\| <math>\pi(n) \sim \frac{n}{\operatorname{Li}(n)}</math>, whereas <math>\omega(n) = O(\log n)</math>. Thus, we get an asymptotic lower bound of <math>~n/\operatorname{Li}(n)</math>. Note that this estimation relies on the [[prime number theorem]].
	\|-		\|-
	\| upper \|\| <math>n - \sigma_0(n) + 1</math> \|\| <math>\sigma_0(n)</math> is the [[divisor count function]], counting the total number of divisors of <math>n</math> \|\| With the exception of 1, any number in <math>\{1, 2, \dots, n\}</math> cannot be both a divisor of <math>n</math> and relatively prime to <math>n</math>. \|\| Nothing specifically, but it does show that for non-primes, there is a relatively sharp demarcation between <math>n</math> and <math>\varphi(n)</math> (in terms of differences, not ratios).		\| upper \|\| <math>n - \sigma_0(n) + 1</math> \|\| <math>\sigma_0(n)</math> is the [[divisor count function]], counting the total number of divisors of <math>n</math> \|\| With the exception of 1, any number in <math>\{1, 2, \dots, n\}</math> cannot be both a divisor of <math>n</math> and relatively prime to <math>n</math>. \|\| Nothing specifically, but it does show that for non-primes, there is a relatively sharp demarcation between <math>n</math> and <math>\varphi(n)</math> (in terms of differences, not ratios).

Vipul: /* Inequalities */

2014-01-29T22:30:35Z

Inequalities

← Older revision		Revision as of 22:30, 29 January 2014
Line 97:		Line 97:
	===Inequalities===		===Inequalities===

	* <math>~~\varphi(n) \ge~~ \pi(n) - \omega(n)</math>~~: Here,~~ <math>\pi(n)</math> is the [[prime-counting function]], and counts the number of primes less than or equal to <math>n</math>, while <math>\omega(n)</math> is the [[prime divisor count function]] of <math>n</math>.
	* <math>\~~varphi~~(n) \le n - \sigma_0(n) + 1</math>~~: Here,~~ <math>\sigma_0(n)</math> is the [[divisor count function]], counting the total number of divisors of <math>n</math>.		{\| class="sortable" border="1"
			! Nature of bound (upper bound or lower) !! Formula !! Arithmetic functions used !! Explanation !! Asymptotic implication
			\|-
			\| lower \|\| <math>\pi(n) - \omega(n)</math>\|\| <math>\pi(n)</math> is the [[prime-counting function]], and counts the number of primes less than or equal to <math>n</math>, while <math>\omega(n)</math> is the [[prime divisor count function]] of <math>n</math>. \|\| Any prime less than or equal to <math>n</math> that does ''not'' divide <math>n</math> must be relatively prime to <math>n</math>. \|\| <math>\pi(n) \sim \frac{n}{\operatorname{Li}(n)}</math>, whereas <math>\omega(n) = O(\log n)</math>. Thus, we get an asymptotic lower bound of <math>~n/\operatorname{Li}(n)</math>.
			\|-
			\| upper \|\| <math>n - \sigma_0(n) + 1</math> \|\| <math>\sigma_0(n)</math> is the [[divisor count function]], counting the total number of divisors of <math>n</math> \|\| With the exception of 1, any number in <math>\{1, 2, \dots, n\}</math> cannot be both a divisor of <math>n</math> and relatively prime to <math>n</math>. \|\| Nothing specifically, but it does show that for non-primes, there is a relatively sharp demarcation between <math>n</math> and <math>\varphi(n)</math> (in terms of differences, not ratios).
			\|}

	==Relation with properties of numbers==		==Relation with properties of numbers==

Vipul: /* Dirichlet series */

2014-01-29T22:24:35Z

Dirichlet series

← Older revision		Revision as of 22:24, 29 January 2014
Line 120:		Line 120:
	This simplifies to:		This simplifies to:

	<math>\sum_{n \in mathbb{N}} \frac{\varphi(n)}{n^s} = \frac{\zeta(s - 1)}{\zeta(s)}</math>.		<math>\sum_{n \in \mathbb{N}} \frac{\varphi(n)}{n^s} = \frac{\zeta(s - 1)}{\zeta(s)}</math>.

	This identity holds not just for the formal Dirichlet series, but also for their analytic continuations, and is valid universally for the meromorphic functions.		This identity holds not just for the formal Dirichlet series, but also for their analytic continuations, and is valid universally for the meromorphic functions.

	==Algebraic significance==		==Algebraic significance==

Vipul: /* Relations expressed in terms of Dirichlet products */

2014-01-29T22:23:53Z

Relations expressed in terms of Dirichlet products

← Older revision		Revision as of 22:23, 29 January 2014
Line 92:		Line 92:
	\| <math>E</math> (identity map, sends everything to itself) \|\| <math>\varphi</math> \|\| <math>E</math> \|\| <math>\sigma_1</math> \|\| no name		\| <math>E</math> (identity map, sends everything to itself) \|\| <math>\varphi</math> \|\| <math>E</math> \|\| <math>\sigma_1</math> \|\| no name
	\|-		\|-
	\| <math>\sigma_1<math> \|\| <math>E</math> \|\| <math>\sigma_1</math> \|\| no name \|\| no name		\| <math>\sigma_1</math> \|\| <math>E</math> \|\| <math>\sigma_1</math> \|\| no name \|\| no name
	\|}		\|}