โปรแกรม C++ เพื่อใช้ทฤษฎีบทออยเลอร์

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

อัลกอริทึม

Begin
   Take input to find modular multiplicative inverse
   Take input as modular value
   Perform inverse array function:
   modInverse(x + 1, 0);
   modInverse[1] = 1;
   for i = 2 to 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