| Displaying 1-3 of 3 results found.
page
1
Primes p such that x^49 = 2 has no solution mod p, but x^7 = 2 has a solution mod p.
+10
12
4999, 6959, 7351, 11467, 15583, 16073, 20483, 21169, 21757, 30773, 35771, 37339, 38711, 41161, 45179, 46649, 48119, 51157, 51647, 57527, 58997, 64877, 75167, 75853, 80263, 83791, 84869, 85751, 86927, 93983, 95747, 105253, 110251, 115837
MATHEMATICA
Select[Prime[Range[PrimePi[120000]]], ! MemberQ[PowerMod[Range[#], 49, #], Mod[2, #]] && MemberQ[PowerMod[Range[#], 7, #], Mod[2, #]] &] (* Vincenzo Librandi, Sep 21 2013 *)
PROG
(PARI) forprime(p=2, 116000, x=0; while(x<p&&x^7%p!=2%p, x++); if(x<p, y=0; while(y<p&&y^(7^2)%p!=2%p, y++); if(y==p, print1(p, ", "))))
(PARI)
N=10^6; default(primelimit, N);
ok(p, r, k1, k2)={
if ( Mod(r, p)^((p-1)/gcd(k1, p-1))!=1, return(0) );
if ( Mod(r, p)^((p-1)/gcd(k2, p-1))==1, return(0) );
return(1);
}
forprime(p=2, N, if (ok(p, 2, 7, 7^2), print1(p, ", ")));
Primes p such that x^7 = 2 has a solution mod p.
+10
11
2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 47, 53, 59, 61, 67, 73, 79, 83, 89, 97, 101, 103, 107, 109, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 199, 223, 227, 229, 233, 241, 251, 257, 263, 269, 271, 277, 283, 293, 307, 311, 313, 317, 331
COMMENTS
Coincides with sequence of "primes p such that x^49 = 2 has a solution mod p" for first 572 terms, then diverges.
a(98) = 631 is the first such prime that is congruent to 1 (mod 7). - Georg Fischer, Jan 06 2022
MATHEMATICA
ok[p_]:= Reduce[Mod[x^7 - 2, p] == 0, x, Integers]=!=False; Select[Prime[Range[100]], ok] (* Vincenzo Librandi, Sep 13 2012 *)
PROG
(Magma) [p: p in PrimesUpTo(400) | exists{x: x in ResidueClassRing(p) | x^7 eq 2}]; // Bruno Berselli, Sep 12 2012
CROSSREFS
For primes p such that x^m == 2 mod p has a solution for m = 2,3,4,5,6,7,... see A038873, A040028, A040098, A040159, A040992, A042966, ...
Number of normal bases in GF(2^n) that are Gaussian normal bases.
+10
0
1, 1, 1, 2, 1, 4, 1, 0, 3, 8, 3, 16, 5, 16, 15, 0, 17, 48, 27, 128, 63, 192, 89, 0, 205, 637, 171, 1011, 565
COMMENTS
A type-t Gaussian normal basis (GNB) exists for GF(2^n) if p=n*t+1 is prime and gcd(n,(p-1)/ord(2 mod p))==1. In practice one finds (for fixed n) infinitely many t corresponding to some GNB. As there are only finitely many normal bases for fixed n the GNBs for different t are not in general different but correspond to a finite set of field polynomials. This sequence gives the number of field polynomials (equivalently, mod-2 reduced multiplication matrices) that correspond to some GNB.
The sequence was computed by determining all field polynomials for types t <= n*500 and discarding duplicate polynomials. Note that there is no guarantee that the used bound (500*n) leads to discovery of all polynomials.
An efficient method to determine (for fixed n) whether two types, say t1 and t2, correspond to the same polynomial would be of great interest.
A computation using the bound t<=2000 gave a(22)=192 (the old value was 191), so the sequence was corrected past that term and truncated after a(29). [ Joerg Arndt, May 16 2011]
LINKS
Joerg Arndt, Fxtbook, section 42.9 "Gaussian normal bases", pp. 914-920.
FORMULA
a(8*n) = 0 (there is no GNB for multiples of eight).
EXAMPLE
For n=5 there is just one field polynomial (x^5 + x^4 + x^2 + x + 1),
for p in {11, 31, 41, 61, 71, 101, 131, ...} ( A040160). For n=7 there is just one field polynomial (x^7 + x^6 + x^4 + x + 1),
for p in {29, 43, 71, 113, 127, 197,...} ( A042967). For n=11 there are three GNBs:
x^11 + x^10 + x^8 + x^4 + x^3 + x^2 + 1
for p in {23, 463, 661, 859, 881, 1409, 1453, 2179, ...},
x^11 + x^10 + x^8 + x^5 + x^2 + x + 1
for p in {67, 89, 353, 727, 947, 1277, 1607, 1783, 1871, ...}, and
x^11 + x^10 + x^8 + x^7 + x^6 + x^5 + 1
for p in {199, 397, 419, 617, 683, 991, 1123, 2003, 2069, 2113, ...}.
Search completed in 0.005 seconds
|