//ax=b mod m işleminin (yani modülerde ters alma işleminin)//euler-fermat teoremine göre genişletilmesi//Euler-Fermat Teoremi:
//a ve m aralarında asal ise
//x=b*a^(U(m)-1) mod m
//U(n)=n*(1-1/asalçarpan1)*(1-1/asalçarpan2) kaç tane asal çarpanı varsa//örneğin U(45)=45*(1-1/5)*(1-1/3)#include<stdio.h>
int main(){
int a,m,b,um=0,temp,x,ustel=1;
printf("\nax=b mod m isleminin Euler-Fermat Teoremine gore genisletilmesi\n\n");
printf("\nTersi alinacak sayiyi giriniz(a):");
scanf("%d",&a);
printf("\nHangi moda gore alinacak(m):");
scanf("%d",&m);
printf("\nb katsayisini giriniz:");
scanf("%d",&b);
int sayac=0,l,ks;
//aralarında asla ise kontrolif(a<m)
ks=a;
if(m<a)
//küçük sayiyi bulduralım ki döngü daha az çalışsın.ks=m;
for(l=2;l<=ks;++l)
if(a%l==0 && m%l==0)
//aralarında asal mı??sayac=1;
if (sayac==0)
//------------------aralarında asal ise{
temp=m;
//mod kısmı daha sonra işimize yarayacak,geçici değişkende tutalımint i,j=0;
//asal çarpanları bulan kısımint asalcarpan[20];
for(i=2;i<=m;i++){
if(m%i==0){
asalcarpan[j]=i;
j=j++;
m=m/i;
}}
//asal çarpanları bulan kısım sonuum=temp;
//mod olan m' nin ilk halini atıyoruzint ii,jj;
for(ii=0;ii<j;++ii)
//U(m) yi buluyoruzum=(um*asalcarpan[ii]-1)/asalcarpan[ii];
//um=um*(1-1/asalcarpan[ii]);for(jj=1;jj<um;jj++)
//a^(U(m)-1) işlemini yapıyoruzustel=ustel*a;
x=(b*ustel)%temp;
//son olarak x' i buluyoruzprintf("\nx=%d mod %d\n",x,temp);
}
//if sonuelse
printf("\nSayilar aralarinda asal degil,Fermat-Euler Teoremine gore cozulemez,baska yontem deneyin:::\n");
return 0;
}
