باقی‌مانده تقسیم 3 به توان 100 را بر 15 به دست آورید.

برای به دست آوردن باقی‌مانده تقسیم 3 به توان 100 بر 15، از خواص حسابان ماژولار و قاعده کوچک فرمی (قاعده باقی‌مانده) استفاده می‌کنیم. قاعده کوچک فرمی: اگر a و b اعداد صحیح باشند و m یک عدد طبیعی باشد و a قابل تقسیم بر m باشد، آنگاه: a^k ≡ (a^(k mod φ(m))) (mod m) که در این جا φ(m) نشان‌دهنده تابع اویلر اعداد کوچک‌تر از m است. برای محاسبه باقی‌مانده تقسیم 3 به توان 100 بر 15، ابتدا باقی‌مانده تقسیم 3 به 15 را به دست می‌آوریم: 3 mod 15 = 3 حالا برای به دست آوردن باقی‌مانده تقسیم 3 به توان 100 بر 15، از قاعده کوچک فرمی استفاده می‌کنیم: 3^100 ≡ (3^(100 mod φ(15))) (mod 15) حالا باید مقدار φ(15) را محاسبه کنیم. تابع اویلر یک عدد n را تعداد اعداد صحیح مثبت کوچک‌تر از n می‌شمارد که با n ارتباطی اولیه ندارند. برای محاسبه تابع اویلر یک عدد n، از این رابطه استفاده می‌کنیم: φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk) که در این جا p1، p2، ...، pk تمام اعداد اول متمایز هستند که n را تقسیم می‌کنند. برای محاسبه φ(15)، باید اعداد اول متمایزی که 15 را تقسیم می‌کنند پیدا کنیم: 1. 15 تقسیم بر 3 نمی‌شود. 2. 15 تقسیم بر 5 می‌شود. بنابراین: φ(15) = 15 * (1 - 1/3) * (1 - 1/5) = 15 * (2/3) * (4/5) = 15 * (8/15) = 8 حالا با توجه به مقادیری که به دست آوردیم، می‌توانیم باقی‌مانده تقسیم 3 به توان 100 بر 15 را به دست آوریم: 3^100 ≡ (3^(100 mod 8)) (mod 15) حالا محاسبه مقدار (100 mod 8): 100 mod 8 = 4 پس داریم: 3^100 ≡ (3^4) (mod 15) حالا محاسبه 3^4: 3^4 = 81 و در نهایت محاسبه باقی‌مانده تقسیم 3 به توان 100 بر 15: 81 mod 15 = 6 بنابراین، باقی‌مانده تقسیم 3 به توان 100 بر 15 برابر با 6 است.