primes with Child's Binomial Theorem

[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;
}

[=?utf-8?B?RXJkaW7Dpw==?=]

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.bl ogspot.com
-----------------
On 24 Mart, 13:22, Carramba <u...@example.n etwrote:

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;

}

[Carramba]

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.bl ogspot.com
-----------------
On 24 Mart, 13:22, Carramba <u...@example.n etwrote:

>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;

}

[Barry Schwarz]

On Sat, 24 Mar 2007 12:22:22 +0100, Carramba <us**@example.n etwrote:

>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

[Carramba]

Barry Schwarz wrote:

On Sat, 24 Mar 2007 12:22:22 +0100, Carramba <us**@example.n etwrote:

>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

[Martin Ambuhl]

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;
}