โปรแกรม C++ ใช้ทฤษฎีบทของออยเลอร์ (Euler's Theorem)

นี่คือโปรแกรม C++ ที่สาธิตการใช้งานทฤษฎีบทของออยเลอร์ (Euler Theorem) ตัวเลขและโมดูลัสต้องเป็น coprime เพื่อให้ modular multiplicative inverse มีอยู่

อัลกอริทึม

Begin
    รับ input หา modular multiplicative inverse
    รับ input เป็น modular value
    ทำ inverse array function: modInverse(x + 1, 0); modInverse[1] = 1;
    for i = 2 ถึง x
        modInverse[i] = (-(y / i) * modInverse[y mod i]) mod y + y
    return modInverse
End

ตัวอย่างโค้ด

#include <iostream>
#include <vector>
using namespace std;

vector<int> inverseArray(int x, int y) {
    vector<int> modInverse(x + 1, 0);
    modInverse[1] = 1;
    for (int i = 2; i <= x; i++) {
        modInverse[i] = (-(y / i) * modInverse[y % i]) % y + y;
    }
    return modInverse;
}

int main() {
    vector<int>::iterator it;
    int a, m;
    cout<<"Enter number to find modular multiplicative inverse: ";
    cin>>a;
    cout<<"Enter Modular Value: ";
    cin>>m;
    cout<<inverseArray(a, m)[a]<<endl;
}

ผลลัพธ์

Enter number to find modular multiplicative inverse: 26
Enter Modular Value: 7
7