מה זה שאר p 12 ^ (p-1), כאשר p הוא ראש?

מה זה שאר p 12 ^ (p-1), כאשר p הוא ראש?
Anonim

תשובה:

השאר שווה ל #0# מתי # p # הוא גם #2# או #3#, והוא שווה ל #1# עבור כל מספרים ראשוניים אחרים.

הסבר:

קודם כל בעיה זו יכולה להיות מחדש כמו צורך למצוא את הערך של # 12 ^ (p-1) mod p # איפה # p # הוא מספר ראשוני.

כדי לפתור בעיה זו אתה צריך לדעת אוילר של משפט. משפט אוילר קובע כי #a ^ { varphi (n)} - = 1 mod n # עבור כל מספר שלם # a # ו # n # כי הם coprime (הם לא חולקים כל הגורמים). אולי אתה תוהה מה # varphi (n) # J זוהי למעשה פונקציה הידועה בשם הפונקציה הטוטלית. הוא מוגדר להיות שווה למספר של מספרים שלמים # <= n # כך מספרים שלמים אלה הם coprime # n #. זכור כי המספר #1# נחשב coprime לכל מספרים שלמים.

עכשיו שאנחנו יודעים אוילר של משפט, אנחנו יכולים ללכת על פתרון בעיה זו.

שים לב כי כל primes אחרים מאשר #2# ו #3# הם עם Coprime #12#. בואו לשים בצד 2 ו 3 מאוחר יותר להתמקד בשאר primes. מאז אלה primes אחרים הם coprime עד 12, אנחנו יכולים להחיל את אוילר של משפט להם:

# 12 ^ {varphi (p)} - = 1 mod p #

מאז # p # הוא מספר ראשוני, # varphi (p) = p-1 #. זה הגיוני כי כל מספר פחות ממספר ראשוני יהיה coprime עם זה.

לכן, עכשיו יש לנו # 12 ^ {p-1} - = 1 mod p #

את הביטוי הנ"ל ניתן לתרגם # 12 ^ {p-1} # מחולק ב # p # יש שארית #1#.

עכשיו אנחנו רק צריכים להסביר #2# ו #3#, אשר כפי שאמרת קודם לכן, שניהם היו שאריות של #0#.

לכן, בסך הכל הוכחנו את זה # 12 ^ {p-1} # מחולק ב # p # איפה # p # הוא מספר ראשוני יש שארית #0# כאשר p הוא גם #2# או #3# ויש לו שארית #1# אחרת.