By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,128 Members | 1,224 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,128 IT Pros & Developers. It's quick & easy.

primes with Child's Binomial Theorem

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;
}
Mar 24 '07 #1
Share this Question
Share on Google+
5 Replies


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;

}

Mar 24 '07 #2

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;

}
Mar 24 '07 #3

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
Mar 24 '07 #4

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
Mar 25 '07 #5

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;
}
Mar 25 '07 #6

This discussion thread is closed

Replies have been disabled for this discussion.