455,128 Members | 1,224 Online 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 #include void id_prime(int i); int power (int base, int n) ; int i, p ; int index = 0; int expect = {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
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 #include void id_prime(int i); int power (int base, int n) ; int i, p ; int index = 0; int expect = {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 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.. Iguess :) it's some thing wrong in my implementation...hope you can help out :) #include #include void id_prime(int i);int power (int base, int n) ;int i, p ;int index = 0;int expect = {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 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.. Iguess :) it's some thing wrong in my implementation...hope you can help out :) #include You don't appear to use this header. >#include 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 = {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 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.. Iguess :) it's some thing wrong in my implementation...hope you can help out :) #include You don't appear to use this header. >#include 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 = {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 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 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 #include void id_prime(int i); int power (int base, int n) ; int i, p ; int index = 0; int expect = {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. 