Turbo в 08:19, 9 декабря 2013

2013-12-09T08:19:47Z

Turbo: Новая страница: «== Определение == '''Функция Эйлера''' $phi (n)$ — это количество чисел от $1$ до $n$
2013-12-09T07:40:41Z

Новая страница: «== Определение == '''Функция Эйлера''' <math>phi (n)</math> — это количество чисел от <math>1</math> до <math>n</m…»

Новая страница
== Определение ==
'''Функция Эйлера''' <math>phi (n)</math> — это количество чисел от <math>1</math> до <math>n</math>, взаимно простых с <math>n</math>, т.е. это количество таких натуральных чисел из отрезка [1; n], наибольший общий делитель (НОД) которых с <math>n</math> равен единице.

Первые значения этой функции:
<table cellpadding=2 cellspacing=2 border=1>
<tr>
<td><math>n</math></td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
<td>6</td>
<td>7</td>
<td>8</td>
<td>9</td>
<td>10</td>
</tr>
<tr>
<td><math>phi(n)</math></td>
<td>1</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>4</td>
<td>2</td>
<td>6</td>
<td>4</td>
<td>6</td>
<td>4</td>
</tr>
</table>

← Предыдущая		Версия 08:19, 9 декабря 2013
Строка 31:		Строка 31:
	</tr>		</tr>
	</table>		</table>
		+
		+	Далее в ряде [http://oeis.org/A000010 A000010 в энциклопедии OEIS].
		+
		+	== Свойства ==
		+	* Если <math>p</math> — простое число, то <math>phi(p)=p-1</math>.
		+	'''Пояснение''': Это очевидно, т.к. любое число, кроме самого p, взаимно просто с ним.
		+	* Если <math>p</math> — простое, <math>a</math> — натуральное число, то <math>phi(p^a)=p^a-p^{a-1}</math>.
		+	'''Пояснение''': Поскольку с числом <math>p^a</math> не взаимно просты только числа вида <math>pk (k \in \mathcal{N})</math>, которых <math>p^a / p = p^{a-1}</math> штук.
		+	* Если <math>a</math> и <math>b</math> взаимно простые, то <math>phi(ab) = phi(a) phi(b)</math> ("мультипликативность" функции Эйлера).
		+	'''Пояснение''': Этот факт следует из китайской теоремы об остатках.
		+
		+	== Функция Эйлера для произвольного <math>n</math> ==
		+	Функцию Эйлера можно получить для любого <math>n</math> через его факторизацию (разложение <math>n</math> на простые сомножители), используя свойства описанные выше. Если
		+
		+	<math>n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}</math>
		+
		+	(где все <math>p_i</math> — простые), то
		+
		+	<math>phi(n) = phi(p_1^{a_1}) \cdot phi(p_2^{a_2}) \cdot \ldots \cdot phi(p_k^{a_k})
		+	= (p_1^{a_1} - p_1^{a_1-1}) \cdot (p_2^{a_2} - p_2^{a_2-1}) \cdot \ldots \cdot (p_k^{a_k} - p_k^{a_k-1})
		+	= n \cdot \left( 1-{1\over p_1} \right) \cdot \left( 1-{1\over p_2} \right) \cdot \ldots \cdot \left( 1-{1\over p_k} \right)</math>
		+
		+	== Приложения ==
		+	Самое известное и важное свойство функции Эйлера выражается в теореме Эйлера:
		+	* <math>a^{phi(m)} \equiv 1 \pmod m</math>, где <math>a</math> и <math>m</math> взаимно просты.
		+
		+	В частном случае, когда <math>m</math> простое, теорема Эйлера превращается в так называемую малую теорему Ферма:
		+
		+	* <math>a^{m-1} \equiv 1 \pmod m </math>
		+
		+	== Ссылки ==
		+	* [http://e-maxx.ru/algo/euler_function Функция Эйлера на e-maxx.ru (для программистов)]
		+	* [http://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%B0 Функция Эйлера в Википедии (для математиков)]
		+
		+	== Реализация ==
		+	* Поиск значения функции Эйлера он-лайн (скоро)

Функция Эйлера - История изменений

Turbo в 08:19, 9 декабря 2013