روش های حل مقایسه درجه اول مقایسه های مدولو

در n همان باقیمانده را می دهند.

فرمول های معادل: a و b قابل مقایسه در مدول n اگر تفاوت آنها آ - ببر n بخش پذیر است یا اگر a را می توان به صورت نمایش داد آ = ب + کn ، جایی که ک- مقداری عدد صحیح به عنوان مثال: 32 و −10 مدول 7 قابل مقایسه هستند، زیرا

عبارت "a و b مدول n قابل مقایسه هستند" به صورت زیر نوشته می شود:

ویژگی های برابری مدول

رابطه مقایسه مدول دارای ویژگی هایی است

هر دو عدد صحیح آو بمدول 1 قابل مقایسه

به منظور اعداد آو باز نظر مدول قابل مقایسه بودند n، لازم و کافی است که تفاوت آنها بر قابل تقسیم باشد n.

اگر اعداد و به صورت زوجی در مدول قابل مقایسه باشند n، سپس مجموع آنها و، و همچنین محصولات و همچنین در مدول قابل مقایسه هستند n.

اگر اعداد آو بقابل مقایسه در مدول n، سپس مدرک آنها آ کو ب کاز نظر مدول نیز قابل مقایسه هستند nتحت هر طبیعی ک.

اگر اعداد آو بقابل مقایسه در مدول n، و nتقسیم بر متر، آن آو بقابل مقایسه در مدول متر.

به منظور اعداد آو باز نظر مدول قابل مقایسه بودند n، در قالب تجزیه متعارف آن به عوامل ساده ارائه شده است پ من

لازم و کافی برای

رابطه مقایسه یک رابطه هم ارزی است و بسیاری از ویژگی های برابری های معمولی را دارد. مثلاً می توان آنها را جمع و ضرب کرد: if

با این حال، به طور کلی نمی توان مقایسه ها را بر یکدیگر یا بر اعداد دیگر تقسیم کرد. مثال: با این حال، با کاهش 2، یک مقایسه اشتباه دریافت می کنیم: . قوانین اختصاری برای مقایسه به شرح زیر است.

همچنین اگر مدول‌های مقایسه‌ها با هم مطابقت نداشته باشند، نمی‌توانید عملیاتی را روی مقایسه‌ها انجام دهید.

سایر خواص:

تعاریف مرتبط

کلاس های کسر

مجموعه تمام اعداد قابل مقایسه با آمدول nتماس گرفت کلاس کسر آمدول n ، و معمولاً نشان داده می شود [ آ] nیا . بنابراین، مقایسه معادل برابری طبقات باقیمانده است [آ] n = [ب] n .

از مقایسه مدول nیک رابطه هم ارزی روی مجموعه اعداد صحیح است، سپس طبقات باقیمانده مدول nنشان دهنده کلاس های هم ارزی تعداد آنها برابر است n. مجموعه مدول تمام طبقات باقیمانده nبا یا نشان داده شده است.

عملیات جمع و ضرب با القای عملیات مربوطه در مجموعه:

با توجه به این عملیات مجموعه یک حلقه محدود است، و اگر nمیدان ساده - محدود

سیستم های کسر

سیستم باقیمانده به شما این امکان را می دهد که عملیات حسابی را روی مجموعه محدودی از اعداد بدون فراتر رفتن از محدوده آن انجام دهید. سیستم کامل کسر modulo n هر مجموعه ای از n عدد صحیح است که مدول n غیر قابل مقایسه هستند. معمولاً کوچکترین باقیمانده های غیرمنفی به عنوان یک سیستم کامل از باقیمانده های مدول n در نظر گرفته می شوند.

یا کوچکترین مطلق کسرهای متشکل از اعداد

در صورت عجیب بودن nو اعداد

در صورت زوج n .

حل مقایسه ها

مقایسه درجه اول

در تئوری اعداد، رمزنگاری و سایر زمینه‌های علم، مشکل یافتن راه‌حل‌هایی برای مقایسه‌های درجه اول فرم اغلب مطرح می‌شود:

حل چنین مقایسه ای با محاسبه gcd آغاز می شود (الف، م)=د. در این مورد، 2 مورد ممکن است:

• اگر بچندگانه نیست د، پس مقایسه راه حلی ندارد.
• اگر بچندگانه د، سپس مقایسه دارای یک مدول راه حل منحصر به فرد است متر / دیا همان چیست دراه حل های مدول متر. در این مورد، در نتیجه کاهش مقایسه اصلی توسط دمقایسه این است:

جایی که آ 1 = آ / د , ب 1 = ب / د و متر 1 = متر / د اعداد صحیح هستند و آ 1 و متر 1 نسبتاً اول هستند. بنابراین تعداد آ 1 را می توان مدول معکوس کرد متر 1، یعنی چنین عددی را پیدا کنید ج، که (به عبارت دیگر، ). اکنون راه حل با ضرب مقایسه حاصل در بدست می آید ج:

محاسبه عملی ارزش جمی توان به روش های مختلف پیاده سازی کرد: با استفاده از قضیه اویلر، الگوریتم اقلیدس، نظریه کسرهای ادامه دار (به الگوریتم مراجعه کنید)، و غیره. به طور خاص، قضیه اویلر به شما امکان می دهد مقدار را یادداشت کنید. جمانند:

مثال

برای مقایسه داریم د= 2، بنابراین مدول 22 مقایسه دو راه حل دارد. بیایید 26 را با 4 جایگزین کنیم، قابل مقایسه با مدول 22، و سپس هر 3 عدد را 2 کاهش دهیم:

از آنجایی که 2 برابر مدول 11 است، می توانیم سمت چپ و راست را 2 کاهش دهیم. در نتیجه، یک مدول راه حل 11: , معادل دو راه حل مدول 22: به دست می آوریم.

مقایسه درجه دوم

حل مقایسه‌های درجه دوم به این نتیجه می‌رسد که آیا یک عدد معین یک پسماند درجه دوم است (با استفاده از قانون متقابل درجه دوم) و سپس محاسبه مدول ریشه دوم.

داستان

قضیه باقیمانده چینی که برای قرن ها شناخته شده است، بیان می کند (به زبان ریاضی مدرن) که مدول حلقه باقیمانده حاصل ضرب چندین عدد هم اول است.

مقایسه با یک ناشناخته ایکسبه نظر می رسد

جایی که . اگر آ n قابل تقسیم بر متر، به این می گویند درجهمقایسه ها

با تصمیممقایسه هر عدد صحیحی است ایکس 0 , برای کدام

اگر ایکس 0 مقایسه را برآورده می کند، سپس، با توجه به ویژگی 9 مقایسه، همه اعداد صحیح قابل مقایسه با ایکس 0 مدول متر. بنابراین، تمام راه حل های مقایسه متعلق به یک مدول کلاس باقی مانده است تی، ما آن را به عنوان یک راه حل در نظر خواهیم گرفت. بنابراین، مقایسه به تعداد عناصر موجود در سیستم کامل باقیمانده‌ها راه‌حل دارد که آن را برآورده می‌کند.

مقایسه هایی که مجموعه راه حل های آنها منطبق است نامیده می شوند معادل.

2.2.1 مقایسه درجه اول

مقایسه درجه اول با یک مجهول ایکسبه نظر می رسد

(2.2)

قضیه 2.4. برای اینکه مقایسه حداقل یک راه حل داشته باشد، کافی و لازم است که عدد ب تقسیم بر GCD( آ, متر).

اثباتابتدا ضرورت را اثبات می کنیم. اجازه دهید د = GCD( آ, متر) و ایکس 0 - راه حل مقایسه سپس ، یعنی تفاوت اوه 0 − ب تقسیم بر تی.بنابراین چنین عدد صحیحی وجود دارد q, چی اوه 0 − ب = qm. از اینجا ب= آه 0 − qm. و از د, به عنوان یک مقسوم علیه مشترک، اعداد را تقسیم می کند آو تی،سپس minuend و subtrahend بر تقسیم می شوند د, و بنابراین ب تقسیم بر د.

حالا بیایید کفایت را ثابت کنیم. اجازه دهید د- بزرگترین مقسوم علیه مشترک اعداد آو تی،و ب تقسیم بر د. سپس، با تعریف تقسیم پذیری، اعداد صحیح زیر وجود دارد آ 1 , ب 1 ، تی 1 , چی .

با استفاده از الگوریتم اقلیدسی توسعه یافته، یک نمایش خطی از عدد 1 = gcd( آ 1 , متر 1 ):

برای برخی ایکس 0 , y 0 . بیایید هر دو طرف تساوی آخر را در ضرب کنیم ب 1 د:

یا همان چیست

,

یعنی و راه حل مقایسه است. □

مثال 2.10. مقایسه 9 ایکس= 6 (mod 12) راه حلی دارد زیرا gcd(9, 12) = 3 و 6 بر 3 بخش پذیر است. □

مثال 2.11. مقایسه 6 برابر= 9 (mod 12) هیچ راه حلی ندارد، زیرا gcd(6, 12) = 6، و 9 بر 6 بخش پذیر نیست. □

قضیه 2.5. مقایسه (2.2) قابل حل باشد و د = GCD( آ, متر). سپس مجموعه راه حل های مقایسه (2.2) شامل د کلاس های باقیمانده مدولو تی،یعنی اگر ایکس 0 - یکی از راه حل ها، سپس همه راه حل های دیگر هستند

اثباتاجازه دهید ایکس 0 - حل مقایسه (2.2) یعنی و , . پس چنین چیزی وجود دارد q، چی اوه 0 − ب = qm. در حال حاضر جایگزینی به آخرین برابری به جای ایکس 0 یک راه حل دلخواه از فرم، که در آن، عبارت را به دست می آوریم

, بخشپذیر بر متر. □

مثال 2.12. مقایسه 9 ایکس=6 (mod 12) دقیقاً سه راه حل دارد، زیرا gcd(9, 12)=3. این راه حل ها: ایکس 0 = 2، x 0 + 4 = 6، ایکس 0 + 2∙4=10.□

مثال 2.13. مقایسه 11 ایکس=2 (mod 15) راه حل منحصر به فردی دارد ایکس 0 = 7، زیرا GCD(11،15)=1.□

ما به شما نشان خواهیم داد که چگونه مقایسه های درجه اول را حل کنید. بدون از دست دادن کلیت، فرض می کنیم که GCD( آ, t) = 1. سپس راه حل مقایسه (2.2) را می توان برای مثال با استفاده از الگوریتم اقلیدسی جستجو کرد. در واقع، با استفاده از الگوریتم اقلیدسی توسعه یافته، عدد 1 را به صورت ترکیبی خطی از اعداد نشان می دهیم. آو تی:

بیایید هر دو طرف این برابری را در ضرب کنیم ب, ما گرفتیم: ب = abq + mrb, جایی که abq - ب = - mrb, به این معنا که آ ∙ (bq) = ب(Mod متر) و bq- راه حل مقایسه (2.2).

راه حل دیگر استفاده از قضیه اویلر است. ما دوباره معتقدیم که GCD(a ت)= 1. قضیه اویلر را اعمال می کنیم: . هر دو طرف مقایسه را در ضرب کنید ب: . بازنویسی آخرین عبارت به عنوان ، به دست می آوریم که راه حلی برای مقایسه (2.2) است.

اجازه دهید اکنون GCD( آ, متر) = د>1. سپس آ = آتید, متر = مترتید, جایی که GCD( آ 1 , متر 1) = 1. علاوه بر این، لازم است ب = ب 1 د, برای اینکه مقایسه قابل حل باشد. اگر ایکس 0 - راه حل مقایسه آ 1 ایکس = ب 1 (Mod متر 1)، و تنها، از زمان GCD ( آ 1 , متر 1) = 1، سپس ایکس 0 راه حل و مقایسه خواهد بود آ 1 xd = دسی بی 1 (Mod متر 1), یعنی مقایسه اصلی (2.2). باقی مانده د- 1 راه حل با قضیه 2.5 یافت می شود.

معرفی

§1. مقایسه ماژول

§2. ویژگی های مقایسه

1. ویژگی های مقایسه مستقل از ماژول
2. خواص مقایسه‌ها وابسته به ماژول

§3. سیستم کسر

1. سیستم کامل کسر
2. سیستم کسر کاهش یافته است

§4. قضیه اویلر و فرما

1. تابع اویلر
2. قضیه اویلر و فرما

فصل 2. نظریه مقایسه با یک متغیر

§1. مفاهیم اساسی مربوط به حل مقایسه ها

1. ریشه های مقایسه
2. معادل سازی مقایسه ها
3. قضیه ویلسون

§2. مقایسه درجه اول و راه حل آنها

1. روش انتخاب
2. روش های اویلر
3. روش الگوریتم اقلیدس
4. روش کسر ادامه

§3. سیستم های مقایسه درجه 1 با یک ناشناخته

§4. تقسیم بندی مقایسات درجات بالاتر

§5. ریشه ها و شاخص های ضد مشتق

1. ترتیب کلاس کسر
2. ریشه های اولیه modulo prime
3. شاخص های اول مدولو

فصل 3. کاربرد نظریه مقایسه ها

§1. نشانه های تقسیم پذیری

§2. بررسی نتایج عملیات حسابی

§3. تبدیل کسر معمولی به کسر نهایی

کسری سیستماتیک اعشاری

نتیجه

ادبیات

معرفی

در زندگی ما اغلب مجبوریم با اعداد صحیح و مشکلات مربوط به آنها سر و کار داشته باشیم. در این پایان نامه به نظریه مقایسه اعداد صحیح می پردازم.

دو عدد صحیح که تفاوت آنها مضربی از یک عدد طبیعی معین استمتر قابل مقایسه در مدول نامیده می شوندمتر

کلمه "ماژول" از کلمه لاتین modulus گرفته شده است که در روسی به معنای "اندازه گیری"، "قدر" است.

عبارت "a قابل مقایسه با b modulo m است" معمولاً به صورت a نوشته می شودb (mod m) و مقایسه نامیده می شود.

تعریف مقایسه در کتاب "مطالعات حسابی" توسط K. Gauss بیان شده است. این اثر، که به زبان لاتین نوشته شده بود، در سال 1797 شروع به چاپ کرد، اما این کتاب تنها در سال 1801 منتشر شد، زیرا فرآیند چاپ در آن زمان بسیار کار فشرده و طولانی بود. بخش اول کتاب گاوس به نام "در مورد مقایسه اعداد به طور کلی".

استفاده از مقایسه در مواردی که کافی است در برخی مطالعات اعداد دقیق به مضرب یک عدد معین را بدانید، بسیار راحت است.

به عنوان مثال، اگر ما علاقه مندیم که مکعب یک عدد صحیح a به چه رقمی ختم می شود، کافی است که a را فقط تا مضرب 10 بدانیم و می توانیم از مدول مقایسه 10 استفاده کنیم.

هدف از این کار بررسی تئوری مقایسه ها و بررسی روش های اساسی برای حل مقایسه با مجهولات و همچنین بررسی کاربرد نظریه مقایسه در ریاضیات مدرسه است.

پایان نامه شامل سه فصل است که هر فصل به پاراگراف و پاراگراف به پاراگراف تقسیم می شود.

فصل اول به تشریح مسائل کلی نظریه مقایسه می پردازد. در اینجا مفهوم مقایسه مدول، خواص مقایسه ها، سیستم کامل و کاهش یافته باقیمانده ها، تابع اویلر، قضیه اویلر و فرما را در نظر می گیریم.

فصل دوم به نظریه مقایسه با مجهول اختصاص دارد. مفاهیم اساسی مرتبط با حل مقایسه ها را تشریح می کند، روش هایی را برای حل مقایسه های درجه اول در نظر می گیرد (روش انتخاب، روش اویلر، روش الگوریتم اقلیدسی، روش کسرهای ادامه دار، با استفاده از شاخص ها)، سیستم های مقایسه درجه اول. با یک مجهول، مقایسه درجات بالاتر و غیره.

فصل سوم شامل برخی کاربردهای نظریه اعداد در ریاضیات مدرسه است. علائم تقسیم پذیری، بررسی نتایج اعمال، و تبدیل کسرهای معمولی به کسرهای اعشاری سیستماتیک در نظر گرفته شده است.

ارائه مطالب نظری با تعداد زیادی مثال همراه است که ماهیت مفاهیم و تعاریف معرفی شده را آشکار می کند.

فصل 1. سوالات عمومی تئوری مقایسه

§1. مقایسه ماژول

بگذارید z حلقه اعداد صحیح، m یک عدد صحیح ثابت و m·z مجموعه همه اعداد صحیح مضرب m باشد.

تعریف 1. اگر m a-b را تقسیم کند دو عدد صحیح a و b قابل مقایسه هستند.

اگر اعداد a و b قابل مقایسه با مدول m هستند، a را بنویسید b (mod m).

شرط الف b (mod m) یعنی a-b بر m بخش پذیر است.

a b (mod m)↔(a-b) m

اجازه دهید تعریف کنیم که مدول رابطه‌ی مقایسه‌پذیری m با مدول رابطه‌ی مقایسه‌پذیری (-m) منطبق است (تقسیم‌پذیری بر m معادل بخش‌پذیری بر -m است). بنابراین، بدون از دست دادن کلیت، می توان فرض کرد که m>0.

مثال ها.

قضیه. (نشانه ای از مقایسه اعداد روحی مدول m): دو عدد صحیح a و b مدول m قابل مقایسه هستند اگر و فقط اگر a و b هنگام تقسیم بر m باقیمانده یکسانی داشته باشند.

اثبات

بگذارید باقیمانده ها هنگام تقسیم a و b بر m برابر باشند، یعنی a=mq1+r،(1)

B=mq2+r، (2)

جایی که 0≤r≥m.

(2) را از (1) کم کنیم، a-b= m(q1- q2) به دست می آید، یعنی a-b m یا a b (mod m).

برعکس، اجازه دهید a b (mod m). این بدان معنی است که a-b m یا a-b=mt، t z (3)

b را بر m تقسیم کنید. در (3) b=mq+r را بدست می آوریم، a=m(q+t)+r خواهیم داشت، یعنی با تقسیم a بر m، همان باقیمانده ای حاصل می شود که b را بر m تقسیم می کنیم.

مثال ها.

5=4·(-2)+3

23=4·5+3

24=3·8+0

10=3·3+1

تعریف 2. دو یا چند عدد که با تقسیم بر m باقیمانده‌های یکسانی به دست می‌دهند، باقیمانده‌های مساوی یا مدول m قابل مقایسه نامیده می‌شوند.

مثال ها.

داریم: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m² و (- m²) تقسیم بر m => مقایسه ما صحیح است.

1. ثابت کنید که مقایسه های زیر نادرست هستند:

اگر اعداد با مدول m قابل مقایسه باشند، آنگاه gcd یکسانی با آن دارند.

داریم: 4=2·2، 10=2·5، 25=5·5

GCD(4،10) = 2، GCD(25،10) = 5، بنابراین مقایسه ما نادرست است.

§2. ویژگی های مقایسه

1. ویژگی های مستقل از ماژول مقایسه ها.

بسیاری از ویژگی های مقایسه ها مشابه ویژگی های برابری ها هستند.

الف) بازتاب: الفa (mod m) (هر عدد صحیحآ قابل مقایسه با خودش modulo m)؛

ب) تقارن: اگر الف b (mod m)، سپس b a (mod m)؛

ج) گذرا: اگر الف b (mod m)، و b با (mod m)، سپس a با (mod m).

اثبات

با شرط m/(a-b) و m/ (c-d). بنابراین، m/(a-b)+(c-d)، m/(a+c)-(b+d) => a+c b+d (mod m).

مثال ها.

هنگام تقسیم، باقیمانده را پیدا کنیددر 13.

راه حل: -1 (mod 13) و 1 (mod 13)، سپس (-1)+1 0 (mod 13)، یعنی باقیمانده تقسیمدر 13 0 است.

a-c b-d (mod m).

اثبات

با شرط m/(a-b) و m/(c-d). بنابراین، m/(a-b)-(c-d)، m/(a-c)-(b-d) => (a-c) b-d (mod m).

1. (نتیجه خواص 1، 2، 3). می توانید یک عدد صحیح را به هر دو طرف مقایسه اضافه کنید.

اثبات

اجازه دهید a b (mod m) و k هر عدد صحیحی است. با خاصیت بازتابی

k=k (mod m) و با توجه به خواص 2 و 3 a+k داریم b+k (mod m).

a·c·d (mod m).

اثبات

با شرط، a-b є mz، c-d є mz. بنابراین a·c-b·d = (a·c - b·c)+(b·c-b·d)=(a-b)·c+b·(c-d) є mz، یعنی a·c·d (mod m).

نتیجه. هر دو طرف مقایسه را می توان به یک عدد صحیح غیر منفی افزایش داد: اگر ab (mod m) و s یک عدد صحیح غیر منفی است، سپس a s b s (mod m).

مثال ها.

راه حل: بدیهی است 13 1 (Mod 3)

2 -1 (Mod 3)

5 -1 (Mod 3)، سپس

- · 1-1 0 (Mod 13)

پاسخ: باقیمانده مورد نیاز صفر است و A بر 3 بخش پذیر است.

راه حل:

اجازه دهید ثابت کنیم که 1+ 0 (mod13) یا 1+ 0 (mod 13)

1+ =1+ 1+ =

از 27 1 (mod 13)، سپس 1+ 1+1·3+1·9 (mod 13).

و غیره.

3. هنگام تقسیم با باقیمانده یک عدد، باقیمانده را بیابیددر 24.

ما داریم: 1 (mod 24)، بنابراین

1 (Mod 24)

با اضافه کردن 55 به هر دو طرف مقایسه، دریافت می کنیم:

(Mod 24).

ما داریم: (mod 24)، بنابراین

(Mod 24) برای هر k є N.

از این رو (Mod 24). از زمان (8-)16 (mod 24)، باقیمانده مورد نیاز 16 است.

1. هر دو طرف مقایسه را می توان در یک عدد صحیح ضرب کرد.

2. خواص مقایسه بسته به ماژول.

اثبات

از a b (mod t)، سپس (a - b) t. و از t n ، سپس به دلیل گذرا بودن رابطه تقسیم پذیری(a - b n)، یعنی a b (mod n).

مثال.

وقتی 196 بر 7 تقسیم شد، باقیمانده را پیدا کنید.

راه حل:

دانستن اینکه 196= ، می توانیم 196 بنویسیم(Mod 14). بیایید از ویژگی قبلی، 14 استفاده کنیم 7، ما 196 (mod 7) را دریافت می کنیم، یعنی 196 7.

1. هر دو طرف مقایسه و مدول را می توان در یک عدد صحیح مثبت یکسان ضرب کرد.

اثبات

بگذارید a b (mod t ) و c یک عدد صحیح مثبت است. سپس a-b = mt و ac-bc=mtc یا ac bc (mod mc).

مثال.

تعیین کنید که آیا مقدار یک عبارت است یا خیریک عدد صحیح

راه حل:

بیایید کسرها را به صورت مقایسه نشان دهیم: 4(Mod 3)

1 (Mod 9)

31 (Mod 27)

بیایید این مقایسه ها را ترم به ترم اضافه کنیم (ویژگی 2)، به 124 می رسیم(mod 27) می بینیم که 124 عدد صحیحی نیست که بر 27 بخش پذیر باشد، از این رو معنای عبارتهمچنین یک عدد صحیح نیست.

1. هر دو طرف مقایسه را می توان بر اساس ضریب مشترک آنها تقسیم کرد اگر ضریب هم پرایم نسبت به مدول باشد.

اثبات

اگر حدود cb (mod m)، یعنی m/c(a-b) و عددبا coprime به m، (c,m)=1، سپس m a-b را تقسیم می کند. از این رو، a b (mod t).

مثال.

60 9 (Mod 17)، پس از تقسیم هر دو طرف مقایسه بر 3، دریافت می کنیم:

20 (Mod 17).

به طور کلی، غیرممکن است که هر دو طرف یک مقایسه را بر عددی تقسیم کنیم که همزمان با مدول نیست، زیرا پس از تقسیم ممکن است اعدادی به دست آید که با توجه به یک مدول داده شده غیر قابل مقایسه باشند.

مثال.

8 (Mod 4)، اما 2 (Mod 4).

1. هر دو طرف مقایسه و مدول را می توان با مقسوم علیه مشترک آنها تقسیم کرد.

اثبات

اگر ka kb (mod km)، سپس k (a-b) بر کیلومتر تقسیم می شود. بنابراین a-b بر m بخش پذیر است، یعنی a b (mod t).

اثبات

فرض کنید P (x) = c 0 x n + c 1 x n-1 + ... + c n-1 x+ c n. با شرط a b (mod t)، سپس

a k b k (mod m) برای k = 0, 1, 2, …,n. ضرب دو طرف هر یک از مقایسه های حاصل از n+1 در c n-k ، دریافت می کنیم:

c n-k a k c n-k b k (mod m)، که در آن k = 0، 1، 2، …،n.

با جمع کردن آخرین مقایسه ها، می گیریم: P (a) P (b) (mod m). اگر a (mod m) و c i d i (mod m)، 0 ≤ i ≤n، سپس

(mod m). بنابراین، در مقایسه مدول m، شرایط و عوامل فردی را می توان با اعداد قابل مقایسه با مدول m جایگزین کرد.

در عین حال، باید به این واقعیت توجه داشته باشید که توان های یافت شده در مقایسه ها را نمی توان به این ترتیب جایگزین کرد:

a n c(mod m) و n k(mod m) از آن پیروی نمی کند که a k s (mod m).

Property 11 تعدادی کاربرد مهم دارد. به ویژه، با کمک آن می توان یک توجیه نظری برای علائم تقسیم پذیری ارائه داد. برای توضیح، به عنوان مثال، استخراج آزمون بخش پذیری بر 3 را ارائه می دهیم.

مثال.

هر عدد طبیعی N را می توان به عنوان یک عدد سیستماتیک نشان داد: N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n .

چند جمله ای f(x) = a را در نظر بگیرید 0 x n + a 1 x n-1 + ... + a n-1 x+a n . زیرا

10 1 (mod 3)، سپس توسط ویژگی 10 f (10) f(1) (mod 3) یا

N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n a 1 + a 2 +…+ a n-1 + a n (mod 3)، یعنی برای اینکه N بر 3 بخش پذیر باشد، لازم و کافی است که مجموع ارقام این عدد بر 3 بخش پذیر باشد.

§3. سیستم های کسر

1. سیستم کامل کسر

اعداد باقیمانده مساوی، یا همان چیزی است که مدول m قابل مقایسه است، کلاسی از اعداد مدول m را تشکیل می دهد.

از این تعریف چنین استنباط می شود که همه اعداد در کلاس با همان r باقی مانده مطابقت دارند و اگر به شکل mq+r، q را در تمام اعداد صحیح اجرا کنیم، همه اعداد کلاس را به دست می آوریم.

بر این اساس، با m مقادیر مختلف r، m کلاس اعداد مدول m داریم.

هر عدد از یک کلاس را با توجه به تمام اعداد یک کلاس، مدول باقیمانده m می نامند. باقیمانده ای که در q=0 برابر با r باقی مانده به دست می آید، کوچکترین باقیمانده غیر منفی نامیده می شود.

باقیمانده ρ، کوچکترین در مقدار مطلق، مطلقا کوچکترین باقیمانده نامیده می شود.

بدیهی است که برای r، ρ=r داریم. در r> ρ=r-m داریم. در نهایت، اگر m زوج و r= باشد، سپس هر یک از دو عدد را می توان ρ در نظر گرفتو -m= - .

اجازه دهید از هر کلاس مدول باقیمانده انتخاب کنیمتی یک عدد در یک زمان ما گرفتیم t اعداد صحیح: x 1,…, x m. مجموعه (x 1,…, x t) نامیده می شود سیستم کامل کسر مدول m.

از آنجایی که هر کلاس شامل تعداد نامتناهی باقیمانده است، می توان تعداد نامتناهی سیستم کامل مختلف باقیمانده را برای یک ماژول معین m ساخت که هر یک شاملکسورات.

مثال.

چندین سیستم کامل از کسرهای مدول را تدوین کنیدتی = 5. ما کلاس داریم: 0، 1، 2، 3، 4.

0 = {... -10, -5,0, 5, 10,…}

1= {... -9, -4, 1, 6, 11,…}

بیایید چندین سیستم کامل کسر ایجاد کنیم و از هر کلاس یک کسر برداریم:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

10, -9, -8, -7, -6

5, -4, -3, -2, -1

و غیره.

رایج ترین:

1. سیستم کامل از حداقل باقیمانده های غیر منفی: 0، 1، t -1 در مثال بالا: 0، 1، 2، 3، 4. ایجاد این سیستم از باقیمانده ها ساده است: شما باید تمام باقیمانده های غیر منفی را که هنگام تقسیم بر m به دست می آیند، یادداشت کنید.
2. سیستم کامل با حداقل باقیمانده های مثبت(کوچکترین کسر مثبت از هر کلاس گرفته می شود):

1، 2، …، م. در مثال ما: 1، 2، 3، 4، 5.

1. یک سیستم کامل از کسر مطلقا حداقل.در مورد m فرد، کوچکترین مطلق باقیمانده ها در کنار هم نشان داده می شوند.

- ,…, -1, 0, 1,…, ,

و در صورت زوج m یکی از دو ردیف

1, …, -1, 0, 1,…, ,

, …, -1, 0, 1, …, .

در مثال داده شده: -2، -1، 0، 1، 2.

اجازه دهید اکنون ویژگی های اساسی سیستم کامل باقیمانده ها را در نظر بگیریم.

قضیه 1 . هر مجموعه ای از m اعداد صحیح:

x l , x 2 ,…, x m (1)

مدول m جفتی غیرقابل مقایسه، یک سیستم کامل از باقیمانده های مدول m را تشکیل می دهد.

اثبات

1. هر یک از اعداد مجموعه (1) متعلق به یک کلاس خاص است.
2. هر دو عدد x i و x j از (1) با یکدیگر غیر قابل مقایسه هستند، یعنی به کلاس های مختلف تعلق دارند.
3. m اعداد در (1) وجود دارد، یعنی همان تعداد کلاس های مدولو وجود داردتی.

x 1، x 2،…، x t - سیستم کامل کسر مدول m.

قضیه 2. اجازه دهید (a, m) = 1, b - عدد صحیح دلخواه؛ سپس اگر x 1، x 2،…، x t یک سیستم کامل از باقی مانده های مدول m، سپس مجموعه ای از اعداد تبر است 1 + b، تبر 2 + b،…، تبر m + b همچنین یک سیستم کامل از باقیمانده مدول m است.

اثبات

در نظر بگیریم

تبر 1 + b، تبر 2 + b،…، تبر m + b (2)

1. هر یک از اعداد مجموعه (2) متعلق به یک کلاس خاص است.
2. هر دو عدد ax i +b و ax j + b از (2) با یکدیگر غیر قابل مقایسه هستند، یعنی متعلق به کلاس های مختلف هستند.

در واقع، اگر در (2) دو عدد وجود داشته باشد که

تبر i +b ax j + b (mod m)، (i = j)، سپس دریافت می کنیم ax i ax j (mod t). از آنجایی که (a, t) = 1، سپس ویژگی مقایسه می تواند هر دو بخش مقایسه را کاهش دهدآ . x i x j (mod m) را دریافت می کنیم.

با شرط x i x j (mod t) در (i = j)، زیرا x 1، x 2، ...، x m - یک سیستم کامل از کسر.

1. مجموعه اعداد (2) شاملتی اعداد، یعنی به تعداد کلاس‌های modulo m.

بنابراین، تبر 1 + ب، تبر 2 + ب،...، تبر m + ب - سیستم کامل باقیمانده مدولو m.

مثال.

فرض کنید m = 10، a = 3، b = 4.

بیایید سیستم کاملی از باقیمانده های مدول 10 را در نظر بگیریم، به عنوان مثال: 0، 1، 2،…، 9. بیایید اعداد فرم را بسازیم.تبر + ب. ما به دست می آوریم: 4، 7، 10، 13، 16، 19، 22، 25، 28، 31. مجموعه اعداد حاصل یک سیستم کامل از باقیمانده مدول 10 است.

1. سیستم داده شده از کسر.

اجازه دهید قضیه زیر را اثبات کنیم.

قضیه 1.

اعداد از همان کلاس باقیمانده مدول m دارای بزرگترین مقسوم علیه مشترک با m هستند: اگر a ب (mod m)، سپس (a, m) = (b, m).

اثبات

بگذارید a b (mod m). سپس a = b +mt، جایی که t є z. از این برابری نتیجه می شود که (الف t) = (b، t).

در واقع، اجازه دهید δ یک مقسوم علیه مشترک a و m باشد، سپس aδ, m δ. از آنجایی که a = b + mt، سپس b=a-mt، بنابراین bδ. بنابراین هر مقسوم علیه مشترک اعداد a و m مقسوم علیه مشترک m و b است.

برعکس، اگر m δ و b δ، a = b +mt بر δ بخش پذیر است و بنابراین هر مقسوم علیه مشترک m و b مقسوم علیه مشترک a و m است. قضیه ثابت شده است.

تعریف 1. بزرگترین مقسوم علیه مدول مشترک t و هر عدد a از این دسته از کسر توسطتی بزرگترین مقسوم علیه مشترک نامیده می شودتی و این دسته از کسورات.

تعریف 2. کلاس باقیمانده a modulo t coprime به مدول نامیده می شودمتر ، اگر بزرگترین مقسوم علیه مشترک باشد a و t برابر با 1 (یعنی اگر m و هر عددی از a هم اول هستند).

مثال.

اجازه دهید t = 6. کلاس باقیمانده 2 از اعداد (...، -10، -4، 2، 8، 14، ...) تشکیل شده است. بزرگترین مقسوم علیه مشترک هر یک از این اعداد و مدول 6 2 است. بنابراین، (2، 6) = 2. بزرگترین مقسوم علیه مشترک هر عددی از کلاس 5 و مدول 6، 1 است. بنابراین، کلاس 5 هم اول به مدول 6 است. .

اجازه دهید از هر کلاس باقیمانده یک عدد را انتخاب کنیم که با مدول m برابر است. ما سیستمی از کسرها را به دست می آوریم که بخشی از سیستم کامل کسورات است. به او زنگ می زنندسیستم کاهش یافته باقیمانده modulo m.

تعریف 3. مجموعه‌ای از باقیمانده‌های مدول m، که از هر کوپرایم با یکی گرفته می‌شودتی کلاس باقیمانده برای این ماژول سیستم کاهش یافته باقیمانده نامیده می شود.

از تعریف 3 روشی را برای به دست آوردن سیستم کاهش یافته باقیمانده های مدول دنبال می کند T: لازم است تعدادی سیستم کامل از باقیمانده ها را یادداشت کرده و تمام باقیمانده هایی را که با m همزمان نیستند حذف کنید. مجموعه باقیمانده از کسورات، سیستم کاهش یافته کسر است. بدیهی است که تعداد نامتناهی از سیستم های باقیمانده مدول m را می توان تشکیل داد.

اگر سیستم کامل حداقل غیرمنفی یا کاملاً کمترین باقیمانده را به عنوان سیستم اولیه در نظر بگیریم، سپس با استفاده از روش نشان داده شده، به ترتیب، یک سیستم کاهش یافته با حداقل غیرمنفی یا مطلقاً کمترین باقیمانده باقیمانده را بدست می آوریم.

مثال.

اگر تی = 8، سپس 1، 3، 5، 7 سیستم کاهش یافته از حداقل باقیمانده های غیر منفی است، 1، 3، -3، -1- سیستم کاهش یافته با حداقل کسورات.

قضیه 2.

اجازه دهید تعداد کلاس های coprime به m برابر با k است.سپس هر مجموعه ای از k اعداد صحیح

به صورت جفتی مدول غیرقابل مقایسه m و coprime به m، یک سیستم کاهش یافته از باقیمانده مدول m است.

اثبات

الف) هر عدد در جمعیت (1) متعلق به یک طبقه خاص است.

1. همه اعداد از (1) به صورت جفتی در مدول غیر قابل مقایسه هستندتی، یعنی به کلاس های مختلف modulo m تعلق دارند.
2. هر عدد از (1) همزمان با آن استتی، یعنی همه این اعداد متعلق به کلاس های مختلف coprime تا modulo m هستند.
3. مجموع (1) موجود استک اعداد، یعنی به همان تعداد که سیستم کاهش یافته باقیمانده مدول m باید حاوی باشد.

بنابراین، مجموعه اعداد(1) - کاهش سیستم کسر مدولتی.

§4. تابع اویلر

قضایای اویلر و فرما.

1. تابع اویلر

اجازه دهید با φ نشان دهیم(T) تعداد کلاس های باقیمانده مدول m coprime به m، یعنی تعداد عناصر سیستم کاهش یافته مدول باقیمانده t. تابع φ (t) عددی است به او زنگ می زنندتابع اویلر

اجازه دهید به عنوان نمایندگان کلاس های باقیمانده مدول انتخاب کنیم t اعداد 1، ...، t - 1، t. سپس φ (t) - تعداد این اعداد همزمان با t. به عبارت دیگر، φ (t) - تعداد اعداد مثبت که از m تجاوز نکند و نسبتاً اول از m باشد.

مثال ها.

1. اجازه دهید t = 9. سیستم کامل مدول باقیمانده 9 از اعداد 1، 2، 3، 4، 5، 6، 7، 8، 9 تشکیل شده است. به 9. بنابراین چون تعداد این اعداد 6 است، پس φ (9) = 6.
2. اجازه دهید t = 12. سیستم کامل باقیمانده ها از اعداد 1، 2، 3، 4، 5، 6، 7، 8، 9، 10، 11، 12 تشکیل شده است. . این یعنی

φ(12) = 4.

در تی = 1، سیستم کامل باقیمانده ها از یک کلاس 1 تشکیل شده است. مقسوم علیه طبیعی مشترک اعداد 1 و 1 1 است، (1، 1) = 1. بر این اساس، φ(1) = 1 را فرض می کنیم.

بیایید به محاسبه تابع اویلر برویم.

1) اگر t = p یک عدد اول است، سپس φ(p) = p- 1.

اثبات

کسر 1، 2، ...، ص 1 و فقط آنها نسبتا اول با عدد اول هستندآر. بنابراین φ (р) = р - 1.

2) اگر t = p k - قدرت نخست p، سپس

φ(t) = (p - 1) . (1)

اثبات

سیستم کامل کسر مدول t = p k شامل اعداد 1،...، p k - 1، p k تقسیم کننده های طبیعیتی درجه هستندآر. بنابراین تعداد آممکن است یک مقسوم علیه مشترک با m غیر از 1 داشته باشد, فقط در صورتی کهآتقسیم برآر.اما در بین اعداد 1, ... , پک -1 برآرفقط اعداد قابل تقسیم هستندp, 2p, ... , p2 ، ... ربه, که تعداد آنها برابر استآربه: p = pk-1. این به این معنی است که آنها coprime باt = pبهباقی ماندهآربه- آرk-1= صk-l(p-1)شماره. این موضوع را ثابت می کند

φ (ربه) = صk-1(ص-1).

قضیه1.

تابع اویلر ضربی است، یعنی برای اعداد نسبتاً اول m و n، φ (mn) = φ(m) φ (n) داریم.

اثبات

اولین شرط در تعریف تابع ضربی به روشی بی اهمیت برآورده می شود: تابع اویلر برای همه اعداد طبیعی تعریف می شود و φ (1) = 1. ما فقط باید نشان دهیم که اگرنوعپس اعداد همزمان اول

φ (tp)= φ (T) φ (پ).(2)

اجازه دهید سیستم کامل مدول کسر را ترتیب دهیمtpمانندپایکستی -ماتریس ها

1 2 تی

t +1 t +2 2 تن

………………………………

(پ -1) t+1 (پ -1) m+2 جمعه

زیراتیوپنسبتا اول هستند، سپس عددایکسمتقابل فقط باtpآن وقت و تنها زمانی کهایکسمتقابل فقط باتیوایکسمتقابل فقط باپ. اما تعدادکیلومتر + تیمتقابل فقط باتیاگر و تنها اگرتیمتقابل فقط باتی.بنابراین، اعداد coprime به m در ستون هایی قرار دارند که برای آنهاتیاز سیستم کاهش یافته باقیمانده های مدول عبور می کندتی.تعداد چنین ستون هایی برابر با φ است(T).هر ستون سیستم کامل مدول کسر را ارائه می دهدپ.از این کسر φ(پ)coprime باپ.این به این معنی است که تعداد کل اعدادی که نسبتا اول و باتیو با n برابر φ(T)φ(n)

(φ (T)ستون هایی که در هر کدام φ گرفته شده است(پ)شماره). این اعداد، و فقط آنها، هم‌آغاز هستندو غیره.این موضوع را ثابت می کند

φ (tp)= φ (T) φ (پ).

مثال ها.

№1 . صحت برابری های زیر را ثابت کنید

φ(4n) =

اثبات

№2 . معادله را حل کنید

راه حل:زیرا(m) =، آن= ، به این معنا که=600, =75, =3·، سپس x-1=1، x=2،

y-1=2، y=3

پاسخ: x=2، y=3

ما می توانیم مقدار تابع اویلر را محاسبه کنیم(m)، دانستن نمایش متعارف عدد m:

m=.

به دلیل چندگانه بودن(م) داریم:

(m) =.

اما طبق فرمول (1) متوجه می شویم که

-1) و بنابراین

(3)

برابری (3) را می توان به صورت زیر بازنویسی کرد:

زیرا=m، پس(4)

فرمول (3) یا، که یکسان است، (4) چیزی است که ما به دنبال آن هستیم.

مثال ها.

№1 . مقدار آن چقدر است؟

راه حل:,

, =18 (1- ) (1- =18 ، سپس= 1+1+2+2+6+6=18.

№2 . بر اساس ویژگی های تابع عدد اویلر، ثابت کنید که در دنباله اعداد طبیعی مجموعه ای بی نهایت از اعداد اول وجود دارد.

راه حل:با فرض اینکه تعداد اعداد اول یک مجموعه متناهی باشد، فرض می کنیم- بزرگترین عدد اول و اجازه دهید a=حاصلضرب تمام اعداد اول بر اساس یکی از ویژگی های تابع عدد اویلر است

از آنجایی که a≥، پس a یک عدد مرکب است، اما از آنجایی که نمایش متعارف آن شامل همه اعداد اول است، پس=1. ما داریم:

=1 ,

که غیر ممکن است و بدین ترتیب ثابت می شود که مجموعه اعداد اول نامتناهی است.

№3 .معادله را حل کنید، جایی که x=و=2.

راه حل:ما از ویژگی تابع عددی اویلر استفاده می کنیم،

,

و با شرط=2.

اجازه دهید بیان کنیم از=2 ، ما گرفتیم، جایگزین در

:

(1+ -1=120, =11 =>

سپس x=x=11·13=143.

پاسخ:x= 143

2. قضیه اویلر و فرما.

قضیه اویلر نقش مهمی در نظریه مقایسه ایفا می کند.

قضیه اویلر.

اگر یک عدد صحیح a هم اول با m باشد، پس

(1)

اثباتاجازه دهید

(2)

یک سیستم کاهش یافته از باقی مانده مدول m وجود دارد.

اگرآپس یک عدد صحیح همزمان برای m است

(3)

مدول مقایسه اعداد

تهیه شده توسط: ایرینا زوتیکوا

MAOU "لیسه شماره 6"

کلاس: 10 "a"

ناظر علمی: ژلتوا اولگا نیکولاونا

تامبوف

2016

• مسئله
• هدف پروژه
• فرضیه
• اهداف پروژه و برنامه ریزی برای دستیابی به آنها
• مقایسه ها و ویژگی های آنها
• نمونه هایی از مشکلات و راه حل آنها
• سایت ها و ادبیات مورد استفاده

مسئله:

اکثر دانش آموزان به ندرت از مقایسه مدول اعداد برای حل تکالیف غیر استاندارد و المپیاد استفاده می کنند.

هدف پروژه:

با مقایسه مدول اعداد نشان دهید که چگونه می توانید وظایف غیر استاندارد و المپیادی را حل کنید.

فرضیه:

مطالعه عمیق تر موضوع "مقایسه مدول اعداد" به دانش آموزان کمک می کند تا برخی از وظایف غیر استاندارد و المپیاد را حل کنند.

اهداف پروژه و برنامه ریزی برای دستیابی به آنها:

1. موضوع "مقایسه مدول اعداد" را به طور مفصل مطالعه کنید.

2. حل چندین کار غیر استاندارد و المپیادی با استفاده از مقایسه مدول اعداد.

3. یک یادداشت برای دانش آموزان با موضوع "مقایسه مدول اعداد" ایجاد کنید.

4. یک درس با موضوع "مقایسه مدول اعداد" در کلاس 10a برگزار کنید.

5. تکلیف کلاس را با موضوع "مقایسه بر اساس ماژول" بدهید.

6. زمان انجام کار را قبل و بعد از مطالعه مبحث "مقایسه بر اساس ماژول" مقایسه کنید.

7. نتیجه گیری کنید.

قبل از شروع مطالعه دقیق مبحث "مقایسه مدول اعداد" تصمیم گرفتم نحوه ارائه آن را در کتاب های درسی مختلف مقایسه کنم.

• جبر و شروع تحلیل ریاضی. سطح پیشرفته. کلاس دهم (Yu.M. Kolyagin و دیگران)
• ریاضیات: جبر، توابع، تجزیه و تحلیل داده ها. کلاس هفتم (L.G. Peterson و دیگران)
• جبر و شروع تحلیل ریاضی. سطح نمایه کلاس دهم (E.P. Nelin و دیگران)
• جبر و شروع تحلیل ریاضی. سطح نمایه کلاس دهم (G.K. Muravin و دیگران)

همانطور که متوجه شدم برخی از کتب درسی با وجود سطح پیشرفته حتی به این موضوع نمی پردازند. و موضوع به روشن ترین و در دسترس ترین شکل در کتاب درسی توسط L.G. Peterson (فصل: مقدمه ای بر نظریه بخش پذیری) ارائه شده است، بنابراین بیایید سعی کنیم با تکیه بر نظریه این کتاب درسی "مقایسه اعداد" را درک کنیم.

مقایسه ها و ویژگی های آنها

تعریف: اگر دو عدد صحیح a و b هنگام تقسیم بر مقداری m (m>0) باقیمانده یکسانی داشته باشند، آنگاه می گویند کهa و b مدول m قابل مقایسه هستند، و بنویس:

قضیه: اگر و فقط اگر اختلاف a و b بر m بخش پذیر باشد.

خواص:

1. بازتابی بودن مقایسه هاهر عدد a قابل مقایسه با خودش مدول m است (m>0؛ a,m اعداد صحیح هستند).
2. مقایسه های متقارناگر عدد a با عدد b مدول m قابل مقایسه باشد، عدد b با عدد a مدول یکسان قابل مقایسه است (m>0؛ a,b,m اعداد صحیح هستند).
3. گذرا بودن مقایسه هااگر عدد a قابل مقایسه با عدد b مدول m و عدد b با مدول عدد c همان مدول قابل مقایسه باشد، عدد a با عدد c مدول m قابل مقایسه است (m>0؛ a,b,c. ,m اعداد صحیح هستند).
4. اگر عدد a با عدد b مدول m قابل مقایسه باشد، عدد a n قابل مقایسه با عدد b n مدول m(m>0؛ a,b,m-اعداد صحیح؛ n-عدد طبیعی).

نمونه هایی از مشکلات و راه حل آنها.

1. رقم آخر عدد 3 را بیابید 999 .

راه حل:

زیرا پس از تقسیم بر 10، آخرین رقم عدد باقیمانده است

3 999 = 3 3 * 3 996 = 3 3 * (3 4 ) 249 = 7*81 249 7 (mod 10)

(زیرا 34=81 1(mod 10);81 n 1 (mod10) (بر اساس دارایی))

جواب: 7.

2. ثابت کنید که 2 4n -1 بدون باقیمانده بر 15 بخش پذیر است. (Phystech2012)

راه حل:

زیرا 16 1 (Mod 15)، سپس

16n-1 0 (mod 15) (توسط دارایی)؛ 16n= (2 4) n

2 4n -1 0 (Mod 15)

3. ثابت کنید که 12 2n+1 +11 n+2 بدون باقیمانده بر 133 بخش پذیر است.

راه حل:

12 2n+1 =12*144 n 12*11 n (Mod 133) (توسط دارایی)

12 2n+1 +11 n+2 =12*11 n +11 n *121=11 n *(12+121) =11 n *133

شماره (11 n *133) بدون باقیمانده بر 133 تقسیم می شود. بنابراین، (12 2n+1 +11 n+2 ) بدون باقی مانده بر 133 بخش پذیر است.

4. باقیمانده عدد 2 تقسیم بر 15 را پیدا کنید 2015 .

راه حل:

از 16 1 (mod 15)، پس

2 2015 8 (Mod 15)

پاسخ: 8.

5. باقیمانده تقسیم بر 17 عدد 2 را پیدا کنید 2015. (Phystech2015)

راه حل:

2 2015 =2 3 *2 2012 =8*16 503

از 16 -1 (Mod 17)، پس

2 2015 -8 (Mod 15)

8 9 (Mod 17)

جواب: 9.

6- ثابت کنید که عدد 11 است 100 -1 بدون باقیمانده بر 100 بخش پذیر است. (Phystech2015)

راه حل:

11 100 =121 50

121 50 21 50 (mod 100) (بر اساس دارایی)

21 50 =441 25

441 25 41 25 (mod 100) (بر اساس دارایی)

41 25 =41*1681 12

1681 12 (-19) 12 (mod 100) (بر اساس دارایی)

41*(-19) 12 =41*361 6

361 6 (-39) 6 (mod 100) (توسط دارایی)

41*(-39) 6 =41*1521 3

1521 3 21 3 (mod100) (توسط دارایی)

41*21 3 =41*21*441

441 41 (mod 100) (بر اساس دارایی)

21*41 2 =21*1681

1681 -19 (mod 100) (بر اساس دارایی)

21*(-19)=-399

399 1 (mod 100) (بر اساس دارایی)

بنابراین 11 100 1 (Mod 100)

11 100 -1 0 (mod 100) (بر اساس دارایی)

7. سه عدد آورده شده است: 1771,1935,2222. عددی را به گونه ای بیابید که با تقسیم بر آن، باقیمانده سه عدد داده شده برابر شود. (HSE2016)

راه حل:

بگذارید عدد مجهول برابر با a باشد، پس

2222 1935 (mod a); 1935 1771 (mod a); 2222 1771 (mod a)

2222-1935 0 (moda) (بر اساس دارایی)؛ 1935-17710 (moda) (بر اساس دارایی)؛ 2222-17710 (moda) (بر اساس دارایی)

287 0 (mod a); 164 0 (mod a); 451 0 (mod a)

287-164 0 (moda) (بر اساس دارایی)؛ 451-2870 (moda) (بر اساس دارایی)

123 0 (mod a); 164 0 (mod a)

164-123 0 (mod a) (بر اساس ویژگی)

41

مقایسه درجه اول با یک مجهول به شکل زیر است:

f(ایکس) 0 (Mod متر); f(ایکس) = اوه + و n. (1)

حل مقایسه- به معنای یافتن تمام مقادیر x است که آن را برآورده می کند. دو مقایسه که مقادیر یکسان x را برآورده می کنند نامیده می شوند معادل.

اگر مقایسه (1) توسط هر یک راضی باشد ایکس = ایکس 1، سپس (با توجه به 49) همه اعداد قابل مقایسه با ایکس 1، مدول متر: x x 1 (Mod متر). کل این دسته از اعداد در نظر گرفته می شود یک راه حل. با چنین توافقی می توان نتیجه زیر را گرفت.

66.C هم ترازی (1) به اندازه تعداد باقیمانده های سیستم کامل که آن را برآورده می کند، راه حل خواهد داشت.

مثال. مقایسه

6ایکس– 4 0 (Mod 8)

در بین اعداد 0، 1،2، 3، 4، 5، 6، 7، دو عدد سیستم کامل باقیمانده مدول 8 را برآورده می کند: ایکس= 2 و ایکس= 6. بنابراین، این مقایسه دو راه حل دارد:

ایکس 2 (mod 8), ایکس 6 (Mod 8).

مقایسه درجه اول با جابجایی عبارت آزاد (با علامت مخالف) به سمت راست را می توان به شکل کاهش داد.

تبر ب(Mod متر). (2)

مقایسه ای را در نظر بگیرید که شرایط را برآورده کند ( آ, متر) = 1.

با توجه به 66، مقایسه ما به همان اندازه راه حل دارد که بقایای سیستم کامل آن را برآورده می کند. اما کی ایکساز طریق سیستم کامل باقیمانده های مدولو اجرا می شود تی،که اوهاز طریق سیستم کامل کسر (از 60) اجرا می شود. بنابراین، برای یک و تنها یک ارزش ایکس،برگرفته از سیستم کامل، اوهقابل مقایسه خواهد بود ببنابراین،

67. وقتی (a, m) = 1 تبر مقایسه ب(Mod متر)یک راه حل دارد

بگذار حالا ( آ, متر) = د> 1. سپس برای مقایسه (2) برای داشتن راه حل، لازم است (از 55) که بتقسیم بر د،در غیر این صورت مقایسه (2) برای هر عدد صحیح x غیرممکن است . با فرض بنابراین بمضرب د،بگذاریم آ = آ 1 د, ب = ب 1 د, متر = متر 1 دسپس مقایسه (2) معادل این خواهد بود (به اختصار د): آ 1 ایکس ب 1 (Mod متر), که در آن قبلا ( آ 1 , متر 1) = 1, و بنابراین یک مدول راه حل خواهد داشت متر 1 . اجازه دهید ایکس 1- کوچکترین باقیمانده غیرمنفی این محلول مدول m 1 , پس همه اعداد x هستند , تشکیل این محلول در فرم یافت می شود

ایکس ایکس 1 (Mod متر 1). (3)

مدول m، اعداد (3) نه یک راه حل، بلکه بیشتر، دقیقاً به اندازه اعداد (3) در سری 0، 1، 2 راه حل تشکیل می دهند. ...، m – 1 کمترین باقیمانده مدول غیر منفی متراما اعداد زیر (3) در اینجا قرار می گیرند:

ایکس 1 , ایکس 1 + متر 1 , ایکس 1 + 2متر 1 , ..., ایکس 1 + (د – 1) متر 1 ,

آن ها جمع داعداد (3)؛ بنابراین مقایسه (2) دارد دتصمیمات

قضیه را می گیریم:

68. اجازه دهید (a, m) = d. تبر مقایسه b (مد m) غیر ممکن است اگر b بر d بخش پذیر نباشد. وقتی b مضرب d باشد، مقایسه d راه حل دارد.

69. روشی برای حل مقایسات درجه اول بر اساس تئوری کسرهای ادامه دار:

گسترش رابطه به کسری ادامه دار m:a,

و نگاهی به دو کسر منطبق آخر:

با توجه به خواص کسرهای ادامه دار (بر اساس 30 ) ما داریم

بنابراین مقایسه راه حل دارد

برای پیدا کردن، که برای محاسبه کافی است P n- 1 طبق روش مشخص شده در 30.

مثال. بیایید مقایسه را حل کنیم

111ایکس= 75 (mod 321). (4)

در اینجا (111، 321) = 3، و 75 مضرب 3 است. بنابراین، مقایسه سه راه حل دارد.

با تقسیم دو طرف مقایسه و مدول بر 3، مقایسه را بدست می آوریم

37ایکس= 25 (mod 107)، (5)

که ابتدا باید حل کنیم ما داریم

بنابراین، در این مورد n = 4, P n - 1 = 26, ب= 25، و ما یک راه حل برای مقایسه (5) در فرم داریم

ایکس–26 ∙ 25 99 (mod 107).

از این رو راه حل های مقایسه (4) به صورت زیر ارائه می شود:

ایکس 99; 99 + 107; 99 + 2 ∙ 107 (mod 321)،

ایکسº99; 206; 313 (Mod 321).

محاسبه عنصر معکوس توسط یک مدول معین

70.اگر اعداد صحیح باشند آو nهم اول هستند، سپس یک عدد وجود دارد آ'، مقایسه راضی کننده است a ∙ a′ ≡ 1 (Mod n). عدد آ'تماس گرفت معکوس ضربی یک مدول nو نماد استفاده شده برای آن است آ- 1 (Mod n).

محاسبه مقادیر متقابل مدول یک مقدار معین را می توان با حل مقایسه درجه اول با یک مجهول انجام داد که در آن ایکسشماره پذیرفته شد آ'.

برای یافتن راه حل مقایسه

a∙x≡ 1 (Mod متر),

جایی که ( صبح)= 1,

می توانید از الگوریتم اقلیدس (69) یا قضیه فرما- اویلر استفاده کنید که بیان می کند اگر ( صبح) = 1، سپس

آ φ( متر) ≡ 1 (Mod متر).

ایکس ≡ آ φ( متر)–1 (Mod متر).

گروه ها و ویژگی های آنها

گروه‌ها یکی از کلاس‌های طبقه‌بندی هستند که برای طبقه‌بندی ساختارهای ریاضی با ویژگی‌های مشخصه مشترک استفاده می‌شوند. گروه ها دو جزء دارند: یک دسته از (جی) و عملیات() در این مجموعه تعریف شده است.

مفاهیم مجموعه، عنصر و عضویت مفاهیم اساسی تعریف نشده ریاضیات مدرن هستند. هر مجموعه ای با عناصر موجود در آن تعریف می شود (که به نوبه خود می توانند مجموعه نیز باشند). بنابراین، ما می گوییم که یک مجموعه تعریف یا داده می شود اگر برای هر عنصری بتوانیم بگوییم که متعلق به این مجموعه است یا خیر.

برای دو ست الف، بسوابق ب آ, ب آ, ب∩ آ, ب آ, ب \ آ, آ × ببه ترتیب به این معنی است که بزیر مجموعه ای از مجموعه است آ(یعنی هر عنصری از بنیز موجود است در آبه عنوان مثال، مجموعه اعداد طبیعی در مجموعه اعداد واقعی موجود است. علاوه بر این، همیشه آ آ), بزیر مجموعه مناسبی از مجموعه است آ(آنها ب آو ب ≠ آ)، تقاطع بسیاری بو آ(یعنی تمام عناصری که به طور همزمان در آن قرار دارند آ، و در ببه عنوان مثال، محل تلاقی اعداد صحیح و اعداد حقیقی مثبت مجموعه اعداد طبیعی است)، اتحاد مجموعه ها بو آ(یعنی مجموعه ای متشکل از عناصری که در هر دو قرار دارند آ، یا در ب)، تفاوت مجموعه بو آ(یعنی مجموعه عناصری که در آن قرار دارند ب، اما دروغ نگویید آمحصول دکارتی مجموعه ها آو ب(یعنی مجموعه ای از جفت فرم ( آ, ب)، جایی که آ آ, ب ب). از طریق | آ| توان مجموعه همیشه نشان داده می شود آ، یعنی تعداد عناصر در مجموعه آ.

عملیات قاعده ای است که طبق آن هر دو عنصر از یک مجموعه جی(آو ب) با عنصر سوم از G مطابقت دارد: a ب.

بسیاری از عناصر جیبا یک عملیات نامیده می شود گروه، در صورت احراز شرایط زیر.