C
Carramba
theorem states that:
Integer n is prime if and only if (x +1)^n ≡ x^n +1 (mod n) in Z[x].
so I testing it, but values doesn't match ... and I don't se why.. I
guess it's some thing wrong in my implementation...
hope you can help out
#include <stdlib.h>
#include <stdio.h>
void id_prime(int i);
int power (int base, int n) ;
int i, p ;
int index = 0;
int expect[16] = {1, 2, 3 ,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47};
int main(void)
{
int i;
for(i=1;i<50;i++)
{
id_prime(i);
}
return 0;
}
void id_prime(int i)
{
if( (power((4+1), i) % i) == ((power(4, i) +1) % i))
{
printf("PRIME :%d", i);
printf(" EXPECTED : %d\n", expect[index]);
index++;
}
}
int power (int base, int n)
{
p = 1;
for (i = 1; i <= n; ++i)
p *= base;
return p;
}
Integer n is prime if and only if (x +1)^n ≡ x^n +1 (mod n) in Z[x].
so I testing it, but values doesn't match ... and I don't se why.. I
guess it's some thing wrong in my implementation...
hope you can help out
#include <stdlib.h>
#include <stdio.h>
void id_prime(int i);
int power (int base, int n) ;
int i, p ;
int index = 0;
int expect[16] = {1, 2, 3 ,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47};
int main(void)
{
int i;
for(i=1;i<50;i++)
{
id_prime(i);
}
return 0;
}
void id_prime(int i)
{
if( (power((4+1), i) % i) == ((power(4, i) +1) % i))
{
printf("PRIME :%d", i);
printf(" EXPECTED : %d\n", expect[index]);
index++;
}
}
int power (int base, int n)
{
p = 1;
for (i = 1; i <= n; ++i)
p *= base;
return p;
}