ฟังก์ชัน phi ของออยเลอร์
ให้ $n$ เป็นจำนวนเต็มบวก ฟังก์ชัน phi ของออยเลอร์หรือ $\phi(n)$ จะบอกถึงจำนวนของจำนวนนับที่น้อยกว่าหรือเท่ากับ $n$ ที่มีตัวหารร่วมมากกับ $n$ เป็นหนึ่ง
ยกตัวอย่างเช่น $\phi(8)=4$ หมายถึงมีสี่จำนวนที่น้อยกว่าหรือเท่ากับแปดและมีตัวหารร่วมมากกับแปดเป็นหนึ่ง สี่จำนวนดังกล่าวได้แก่ 1 3 5 7
แอปพลิเคชันนี้ใช้คำนวณ $\phi(n)$ จากสูตรผลคูณออยเลอร์ \[ \phi(n) = n \prod_{p|n}\left(1-\frac{1}{p}\right) \] โดย $p$ คือตัวประกอบเฉพาะทั้งหมดของ $n$ ดูการแยกตัวประกอบได้ที่ ตัวประกอบเฉพาะ เราใช้ $\phi(n)$ ในทฤษฎีของออยเลอร์ซึ่งกล่าวว่า ถ้า $a$ และ $n$ เป็นจำนวนเฉพาะสัมพัทธ์ นั่นคือมีตัวหารร่วมมากเป็นหนึ่ง แล้วเราจะได้ความสัมพันธ์ ดังนี้ \[ a^{\phi(n)}\equiv 1\mod{n} \] ซึ่งหมายถึงเมื่อเอา $a$ ยกกำลัง $\phi(n)$ แล้วหารด้วย $n$ จะเหลือเศษ 1
ยกตัวอย่างเช่น 7 กับ 1000 เป็นจำนวนเฉพาะสัมพัทธ์และ $\phi(1000)=400$ เพราะฉะนั้นตามทฤษฎีของออยเลอร์เราจะได้ $7^{400}\equiv 1\mod{1000}$ นั่นคือเลขสามตัวสุดท้ายของ $7^{400}$ คือ 001