P: n/a

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;
}  
Share this Question
P: n/a

Integer n is prime if and only if (x +1)^n â‰¡ x^n +1 (mod n) in Z[x].
In theorem, x must be integer , but do not say all integer satisfy
this condition. Theorem means , for all prime numbers there is an
integer (x) that satisfy this therom.
if( (power((4+1), i) % i) == ((power(4, i) +1) % i))
In here i must be constant ( not c language as in maths ) then find x
like this
for ( i = 0 ; i < 16 ; ++i )
for ( j = 1 ; j < 1000 ; ++j )
{
if( (power((j+1), expect[i]) % expect[i]) == ((power(j,
expect[i]) +1) % expect[i]))
{
// I found it
printf ( "%d", j );
break;
}
}
ErdinÃ§ TaÅŸkÄ±n
erdinctaskin.blogspot.com

On 24 Mart, 13:22, Carramba <u...@example.netwrote:
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;
}
 
P: n/a

ErdinÃ§ wrote:
>Integer n is prime if and only if (x +1)^n â‰¡ x^n +1 (mod n) inZ[x].
In theorem, x must be integer , but do not say all integer satisfy
this condition. Theorem means , for all prime numbers there is an
integer (x) that satisfy this therom.
thanx!
oh ok, but is there any known integers that I can use?
> if( (power((4+1), i) % i) == ((power(4, i) +1) % i))
In here i must be constant ( not c language as in maths ) then find x
like this
for ( i = 0 ; i < 16 ; ++i )
for ( j = 1 ; j < 1000 ; ++j )
{
if( (power((j+1), expect[i]) % expect[i]) == ((power(j,
expect[i]) +1) % expect[i]))
{
// I found it
printf ( "%d", j );
I have only used expect to by able compare output, in this case program
doesn't generate primes
break;
}
}
ErdinÃ§ TaÅŸkÄ±n
erdinctaskin.blogspot.com

On 24 Mart, 13:22, Carramba <u...@example.netwrote:
>theorem states that: Integer n is prime if and only if (x +1)^n â‰¡ x^n +1 (mod n) inZ[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;
}
 
P: n/a

On Sat, 24 Mar 2007 12:22:22 +0100, Carramba <us**@example.netwrote:
>theorem states that: Integer n is prime if and only if (x +1)^n ? x^n +1 (mod n) in Z[x].
What does the '?' mean above? Is it congruent? What is Z[x] and how
does it differ from "normal" arithmetic?
Must it be true for all x or just for some x that you have to find? Is
there any upper limit on x (it doesn't take very long for powers to
exceed the range of an int)?
> 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>
You don't appear to use this header.
>#include <stdio.h>
void id_prime(int i); int power (int base, int n) ;
int i, p ;
These two are used only in power and should be defined there.
>int index = 0; int expect[16] = {1, 2, 3 ,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
These two are used only in id_prime and could (should) be defined
there as static.
> 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))
Is this the way you do arithmetic in Z[x]?
{
printf("PRIME :%d", i);
printf(" EXPECTED : %d\n", expect[index]);
index++;
} }
int power (int base, int n) {
p = 1;
Why are you using a global for this?
for (i = 1; i <= n; ++i)
Why another global?
> p *= base;
return p; }
Remove del for email  
P: n/a

Barry Schwarz wrote:
On Sat, 24 Mar 2007 12:22:22 +0100, Carramba <us**@example.netwrote:
>theorem states that: Integer n is prime if and only if (x +1)^n ? x^n +1 (mod n) in Z[x].
What does the '?' mean above? Is it congruent? What is Z[x] and how
does it differ from "normal" arithmetic?
? just encoding error it should by equivalent
Z[x] means x in Z, were Z is set of integers
Must it be true for all x or just for some x that you have to find? Is
there any upper limit on x (it doesn't take very long for powers to
exceed the range of an int)?
>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>
You don't appear to use this header.
>#include <stdio.h>
void id_prime(int i); int power (int base, int n) ;
int i, p ;
These two are used only in power and should be defined there.
>int index = 0; int expect[16] = {1, 2, 3 ,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
These two are used only in id_prime and could (should) be defined
there as static.
>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))
Is this the way you do arithmetic in Z[x]?
> { printf("PRIME :%d", i); printf(" EXPECTED : %d\n", expect[index]); index++; } }
int power (int base, int n) {
p = 1;
Why are you using a global for this?
> for (i = 1; i <= n; ++i)
Why another global?
> p *= base; return p; }
Remove del for email
 
P: n/a

Carramba wrote:
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 :)
If you were to run the following,
#include <stdio.h>
const unsigned testmax = 300;
int main(void)
{
unsigned n, x, lhp, rhp, rhs, ok, j;
for (n = 1; n <= testmax; n++) {
for (x = ok = 0; x <= n; x++) {
for (lhp = rhp = j = 1, rhs = 2; j <= n; j++) {
lhp *= x + 1;
rhp *= x;
lhp %= n;
rhp %= n;
rhs = rhp == n  1 ? 0 : rhp + 1;
}
if (lhp != rhs) {
ok = 1;
break;
}
}
if (!ok)
printf("%u ok\n", n);
else
printf
("%u fails: (%u+1)^%u = %u (%u), %u^%u +1 == %u"
" (%u).\n",
n, x, n, lhp, n, x, n, rhs, n);
}
return 0;
}
it strongly suggests that the test need only be done for x = 1.
If you can demonstrate that
Integer n is prime if and only if 2^n (mod n) â‰¡ 2 (mod n),
then this shorter program will suffice (some implementations of printf
are broken; if your lines are too long, yours is one of those):
#include <stdio.h>
const unsigned testmax = 1000;
int main(void)
{
unsigned n, lhp, rhs, ok, j, linepos = 0;
const unsigned linelimit = 60;
for (n = 1; n <= testmax; n++) {
ok = 1;
rhs = 2 % n;
for (lhp = j = 1; j <= n; j++) {
lhp *= 2;
lhp %= n;
}
if (lhp == rhs) {
linepos += printf("%u", n);
if (linepos < linelimit)
putchar(' ');
else {
putchar('\n');
linepos = 0;
}
}
}
if (linepos)
putchar('\n');
return 0;
}
>
#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))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This is not the way to do this
{
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;
}
  This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 2144
 replies: 5
 date asked: Mar 24 '07
