ѕункт 17. ѕовна ≥ зведена системи лишк≥в.

” попередньому пункт≥ було зазначено, що в≥дношенн¤ º _m пор≥вн¤нн¤ за дов≥льним модулем m Ї в≥дношенн¤м екв≥валентност≥ на множин≥ ц≥лих чисел. ÷е в≥дношенн¤ екв≥валентност≥ ≥ндукуЇ розбитт¤ множини ц≥лих чисел на класи екв≥валентних м≥ж собою елемент≥в, тобто в один клас обТЇднуютьс¤ числа, що мають при д≥ленн≥ на m однаков≥ залишки. „исло клас≥в екв≥валентност≥ º _m (≥ндекс екв≥валентност≥ º _m) дор≥внюЇ m .

¬изначенн¤. Ѕудь-¤ке число з класу екв≥валентност≥ º _m називаЇтьс¤ лишком за модулем m. —укупн≥сть лишк≥в, уз¤тих по одному з кожного класу екв≥валентност≥ º _m, називаЇтьс¤ повною системою лишк≥в за модулем m (у повн≥й систем≥ лишк≥в усього m чисел). Ѕезпосередньо сам≥ залишки д≥ленн¤ на m називаютьс¤ найменшими нев≥дТЇмними лишками ≥ утворюють повну систему лишк≥в за модулем m. Ћишок r називаЇтьс¤ абсолютно найменшим, ¤кщо ïrï найменший серед модул≥в лишк≥в даного класу.

ѕриклад : Ќехай m = 5 . “од≥:

0, 1, 2, 3, 4 - найменш≥ нев≥дТЇмн≥ лишки;

-2, -1, 0, 1, 2 - абсолютно найменш≥ лишки.

ќбидв≥ наведен≥ множини чисел утвор¤ть повн≥ системи лишк≥в за модулем 5 .

Ћема 1. 1) Ѕудь-¤к≥ m попарно непор≥вн¤льних за модулем m чисел утворюють повну систему лишк≥в за модулем m .

2) якщо а ≥ m взаЇмно прост≥, а x набуваЇ значень з повноњ системи лишк≥в за модулем m, то значенн¤ л≥н≥йноњ форми ах+b, де b - будь-¤ке ц≥ле число, також набувають значень з повноњ системи лишк≥в за модулем m.

ƒоказ. “вердженн¤ 1) Ц очевидне. ƒоведемо твердженн¤ 2). „исел ах+b Ї m штук. ѕокажемо, що вони м≥ж собою непор≥вн¤льн≥ за модулем m. Ќехай дл¤ де¤ких р≥зних x₁ ≥ x₂ з повноњ системи лишк≥в ви¤вилос¤, що ax₁+bº ax₂+b(mod m). “од≥, за властивост¤ми пор≥вн¤нь з попереднього пункту, одержуЇмо:

ax₁ º ax₂ (mod m) ††††††††††††††††††††††††††††††††††††††††††††† x₁ º x₂ (mod m)

Ц протир≥чч¤ з тим, що x₁ ≥ x₂ р≥зн≥ й уз¤т≥ з повноњ системи лишк≥в.

ќск≥льки вс≥ числа з даного класу екв≥валентност≥ º одержуютьс¤ з одного числа даного класу додаванн¤м числа, кратного m, то вс≥ числа даного класу мають з модулем m той самий найб≥льший сп≥льний д≥льник.

¬изначенн¤. «веденою системою лишк≥в за модулем m називаЇтьс¤ сукупн≥сть ус≥х лишк≥в з повноњ системи, взаЇмно простих з модулем m.

«ведену систему звичайно вибирають з найменших нев≥дТЇмних лишк≥в. «розум≥ло, що зведена система лишк≥в за модулем m м≥стить j(m) лишк≥в, де j(m) Ц функц≥¤ ≈йлера Ц к≥льк≥сть чисел, менших за m ≥ взаЇмно простих з m.

ѕриклад. Ќехай m = 42. “од≥ зведеною системою лишк≥в Ї:

1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Ћема 2. 1) Ѕудь-¤к≥ j(m) чисел, попарно непор≥вн¤льн≥ за модулем m ≥ взаЇмно прост≥ з модулем, утворюють зведену систему лишк≥в за модулем m.

2) якщо (a,m)=1 ≥ x набуваЇ значень ≥з зведеноњ системи лишк≥в за модулем m, то ах так само набуваЇ значень ≥з зведеноњ системи лишк≥в за модулем m.

ƒоказ. “вердженн¤ 1) Ц очевидне. ƒоведемо твердженн¤ 2). „исла ах попарно непор≥вн¤льн≥ (доводитьс¤ так само, ¤к лема 1 цього пункту), њх Ї j(m) штук. «розум≥ло, що ус≥ вони взаЇмно прост≥ з модулем, оск≥льки (a,m)=1, (x,m)=1 Þ (ax.m)=1. “аким чином числа ах утвор¤ть зведену систему лишк≥в.

Ћема 3. Ќехай m₁, m₂, ..., m_k Ц попарно взаЇмно прост≥ ≥ m₁ m₂ ...m_k =M₁ m₁=M₂ m₂=...=M_k m_k, де M_j =m₁ ...m_j-1 m_j+1 ...m_k

1) якщо x₁ , x₂ , ..., x_k набувають значень з повних систем лишк≥в за модул¤ми m₁, m₂, ..., m_k в≥дпов≥дно, то значенн¤ л≥н≥йноњ форми M₁ x₁ +M₂ x₂ + ...+M_k x_k набувають значень з повноњ системи лишк≥в за модулем m=m₁ m₂ ...m_k .

2) якщо x₁ , x₂ , ..., x_k† набувають значень ≥з зведених систем лишк≥в за модул¤ми m₁, m₂, ..., m_k в≥дпов≥дно, то значенн¤ л≥н≥йноњ форми M₁ x₁ +M₂ x₂ + ...+M_k x_k набувають значень ≥з зведеноњ системи лишк≥в за модулем m=m₁ m₂ ...m_k .

ƒоказ.

1) ‘орма M₁ x₁ +M₂ x₂ + ...+M_k x_k приймаЇ m₁ m₂ ...m_k=m значень. ѕокажемо, що ц≥ значенн¤ попарно непор≥вн¤льн≥. Ќехай

M₁ x₁ +M₂ x₂ + ...+M_k x_k º M₁ x₁^Ñ +M₂ x₂^Ñ + ...+M_k x_k ^Ñ (mod m)

”с¤ке M_j, що в≥дм≥нне в≥д M_s, кратне до m_s. «абираючи зл≥ва ≥ справа в останньому пор≥вн¤нн≥ що додаютьс¤, кратн≥ до m_s, одержимо:

M_s x_s º M_s x_s^Ñ (mod m_s ) Þ x_s º x_s^Ñ (mod m_s )

Ц протир≥чч¤ з тим, що x_s набуваЇ значень з повноњ системи лишк≥в за модулем m_s.

2). ‘орма M₁ x₁ +M₂ x₂ + ...+M_k x_k приймаЇ j(m₁) j(m₂) †... †j(m_k)=j(m₁ m₂ × ... × m_k )=j(m) (функц≥¤ ≈йлера мультипликативна!) р≥зних значень, що м≥ж собою за модулем m=m₁ m₂ ...m_k попарно непор≥вн¤льн≥. ќстаннЇ доводитьс¤ м≥ркуванн¤ми, аналог≥чними з доказом твердженн¤ 1) ц≥Їњ леми. ќск≥льки (M₁x₁+M₂x₂+...+M_kx_k,m_s)=(M_sx_s,m_s)=1 дл¤ кожного 1£s£ k, то (M₁x₁+M₂x₂+...+M_kx_k ,m_s)=1, отже множина значень форми M₁x₁+M₂x₂+...+M_kx_k утворить зведену систему лишк≥в за модулем m.

Ћема 4. Ќехай x₁, x₂, ...,x_k , x набувають значень з повноњ, а x₁, x₂ ,..., x_k , x Ц набувають значень ≥з зведених систем лишк≥в за модул¤ми m₁, m₂, ..., m_k ≥ m=m₁ m₂ ...m_k в≥дпов≥дно, де (m_i m_j )=1 при i¹j. “од≥ дроби {x₁/m₁+x₂/m₂+...+x_k /m_k } зб≥гаютьс¤ з дробами {x/m}, а дроби {x₁ /m₁ +x₂ /m₂+...+x_k /m_k} зб≥гаютьс¤ з дробами {x /m}.

ƒоказ. ƒоказ обох тверджень леми 4 одержуЇтьс¤ ≥з застосуванн¤м попередньоњ леми 3 п≥сл¤ того, ¤к звести кожну суму {x₁ /m₁ +x₂ /m₂ +...+x_k /m_k } ≥ {x₁ /m₁+x₂ /m₂+...+x_k /m_k } до сп≥льного знаменника:

{x₁ /m₁ +x₂ /m₂ +...+x_k /m_k }={(M₁ x₁ +M₂ x₂ +...+M_k x_k )/m};

{x₁ /m₁ +x₂ /m₂ +...+x_k /m_k }={(M₁ x₁ +M₂ x₂ +...+M_k x_k )/m},

де M_j =m₁ ...m_j-1 m_j+1 ...m_k .

якщо врахувати, що дробов≥ частини чисел, що одержуютьс¤ при д≥ленн≥ на модуль m будь-¤ких двох чисел, пор≥вн¤льних за модулем m, однаков≥ (вони р≥вн≥ r/m, де r Ц найменший нев≥дТЇмний лишок даного класу), то твердженн¤ д≥йсноњ леми очевидн≥.

ѕерейдемо до п≥дсумовуванн¤ комплексних корен≥в m -ого степен¤ з одиниц≥. ѕозначимо через e_k k -ий кор≥нь m- ого степен¤ з одиниц≥:

,

де k=0,1,...,m-1 Ц набуваЇ значень з повноњ системи лишк≥в за модулем m.

ЌагадаЇмо, що сума e₀ +e₁+...+e_m-1 ус≥х корен≥в m -ого степен¤ з одиниц≥ дор≥внюЇ нулю дл¤ будь-¤кого m. Ќехай e₀ +e₁ +...+e_m-1 =a. ѕомножимо цю суму на ненульове число e₁. “аке множенн¤ геометрично в комплексн≥й площин≥ означаЇ поворот правильного m -кутника, у вершинах ¤кого розташован≥ корен≥ e₀, e₁,..., e_m-1, на ненульовий кут 2p/m. ѕри цьому кор≥нь e₀ перейде в кор≥нь e₁, кор≥нь e₁ перейде в кор≥нь e₂, ≥ т.д., а кор≥нь e_m-1 перейде в кор≥нь e₀, тобто сума e₀ + e₁ +...+ e_m-1 не зм≥нитьс¤. ћаЇмо e₁ a=a, зв≥дки a=0.

“еорема 1. Ќехай m>0 - ц≥ле число, a Î Z, x набуваЇ значень з повноњ системи лишк≥в за модулем m. “од≥, ¤кщо а кратне m, то

в ≥ншому випадку, при а не кратному m, .

ƒоказ. ѕри а кратному m маЇмо: a=md ≥

.

якщо а не д≥литьс¤ на m, то розд≥лимо чисельник ≥ знаменник дробу a/m на d Ц найб≥льший сп≥льний д≥льник а ≥ m, одержимо нескоротний др≥б a₁ /m₁. “од≥, за лемою 1, a₁ x набуватиме значень з повноњ системи лишк≥в за модулем m. ћаЇмо:

,

оск≥льки сума вс≥х корен≥в степен¤ m₁ з одиниц≥ дор≥внюЇ нулю.

Ќагадаю, що кор≥нь e_k† m -ого степен¤ з одиниц≥ називаЇтьс¤ перв≥сним, ¤кщо його ≥ндекс k взаЇмно простий з m. ” цьому випадку посл≥довн≥ степен≥ e_k¹, e_k²,..., e_k^m-1 корен¤ e_k утвор¤ть сукупн≥сть корен≥в m -ого степен¤ з одиниц≥ або, ≥ншими словами, e_k Ї породжуючим елементом цикл≥чноњ групи вс≥х корен≥в m -ого степен¤ з одиниц≥.

ќчевидно, що к≥льк≥сть перв≥сних корен≥в m -ого степен¤ з одиниц≥ дор≥внюЇ j(m), де j Ц функц≥¤ ≈йлера, оск≥льки ≥ндекси перв≥сних корен≥в утвор¤ть зведену систему лишк≥в за модулем m.

“еорема 2. Ќехай m>0 Ц ц≥ле число, x набуваЇ значень ≥з зведеноњ системи лишк≥в за модулем m. “од≥ (сума перв≥сних корен≥в степен¤ m):

,

де m(m) Ц функц≥¤ ћеб≥уса.

ƒоказ. Ќехай m=p₁^a1 p₂ ^a2 ...p_k ^ak Ц канон≥чний розклад числа m; m₁ =p₁^a1, m₂ =p₂^a2, m₃=p₃^a3; x_i набуваЇ значень ≥з зведеноњ системи лишк≥в за модулем m_i. ћаЇмо:

ѕри a_s=1 одержуЇтьс¤, що лише кор≥нь e₀=1 не Ї перв≥сним, тому сума вс≥х перв≥сних корен≥в Ї сумою вс≥х корен≥в м≥нус одиниц¤:

“аким чином, ¤кщо m не д≥литьс¤ на r², при r>1, то .

якщо ж ¤кий-небудь показник a_s б≥льший за одиницю (тобто m д≥литьс¤ на r², при r>1), то сума вс≥х перв≥сних корен≥в степен¤ m_s Ї сумою вс≥х корен≥в степен¤ m_s м≥нус сума вс≥х не перв≥сних корен≥в, тобто вс≥х корен≥в де¤кого степен¤, меншого за m_s. якщо m_s =p_s m_s^* , то:

.