Displaying 1-10 of 13 results found.
Order of 2 modulo the n-th prime.
+10
53
2, 4, 3, 10, 12, 8, 18, 11, 28, 5, 36, 20, 14, 23, 52, 58, 60, 66, 35, 9, 39, 82, 11, 48, 100, 51, 106, 36, 28, 7, 130, 68, 138, 148, 15, 52, 162, 83, 172, 178, 180, 95, 96, 196, 99, 210, 37, 226, 76, 29, 119, 24, 50, 16, 131, 268, 135, 92, 70, 94, 292, 102, 155, 156, 316
COMMENTS
In other words, a(n), n >= 2, is the least k such that prime(n) divides 2^k-1.
Concerning the complexity of computing this sequence, see for example Bach and Shallit, p. 115, exercise 8.
Also A002326((p_n-1)/2). Conjecture: If p_n is not a Wieferich prime (1093, 3511, ...) then A002326(((p_n)^k-1)/2) = a(n)*(p_n)^(k-1). - Vladimir Shevelev, May 26 2008 If for distinct i,j,...,k we have a(i)=a(j)=...=a(k) then the number N = p_i*p_j*...*p_k is in A001262 and moreover A137576((N-1)/2) = N. For example, a(16)=a(37)=a(255)=52. Therefore we could take N = p_16*p_37*p_255 = 53*157*1613 = 13421773. - Vladimir Shevelev, Jun 14 2008 Also degree of the irreducible polynomial factors for the polynomial (x^p+1)/(x+1) over GF(2), where p is the n-th prime. - V. Raman, Oct 04 2012 Is this the same as the smallest k > 1 not already in the sequence such that p = prime(n) is a factor of 2^k-1 ( A270600)? If the answer is yes, is the sequence a permutation of the positive integers > 1? - Felix Fröhlich, Feb 21 2016. Answer: No, it is easy to prove that 6 is missing and obviously 11 appears twice. - N. J. A. Sloane, Feb 21 2016 pi( A112927(m)) is the index at which a given number m first appears in this sequence. - M. F. Hasler, Feb 21 2016
REFERENCES
E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I.
Albert H. Beiler, "Recreations in the Theory of Numbers", Dover, 1966; Table 48, page 98, "Exponents to Which a Belongs, MOD p and MOD p^n.
John H. Conway and Richard Guy, "The Book of Numbers", Springer-Verlag, 1996; p. 166: "How does the Cycle Length Change with the Base?". [From Gary W. Adamson, Aug 22 2009] S. K. Sehgal, Group rings, pp. 455-541 in Handbook of Algebra, Vol. 3, Elsevier, 2003; see p. 493.
EXAMPLE
2^2 == 1 (mod 3) and so a(2) = 2;
2^4 == 1 (mod 5) and so a(3) = 4;
2^3 == 1 (mod 7) and so a(4) = 3;
2^10 == 1 (mod 11) and so a(5) = 10; etc.
[Conway & Guy, p. 166]: Referring to the work of Euler, 1/13 in base 2 = 0.000100111011...; (cycle length of 12). - Gary W. Adamson, Aug 22 2009
MAPLE
with(numtheory): [ seq(order(2, ithprime(n)), n=2..60) ];
MATHEMATICA
Reap[Do[p=Prime[i]; Do[If[PowerMod[2, k, p]==1, Print[{i, k}]; Sow[{i, k}]; Goto[ni]], {k, 1, 10^6}]; Label[ni], {i, 2, 5001}]][[2, 1]] (* Zak Seidov, Jan 26 2009 *)
PROG
(PARI) a(n)=if(n<0, 0, k=1; while((2^k-1)%prime(n)>0, k++); k)
(PARI) forprime(p=3, 800, print(factormod((x^p+1)/(x+1), 2, 1)[1, 1])) \\ V. Raman, Oct 04 2012 (GAP) P:=Filtered([1..350], IsPrime);; a:=List([2..Length(P)], n->OrderMod(2, P[n]));; Print(a); # Muniru A Asiru, Jan 29 2019 (Python)
from sympy import n_order, prime
Order of 3 mod n-th prime.
+10
22
1, 0, 4, 6, 5, 3, 16, 18, 11, 28, 30, 18, 8, 42, 23, 52, 29, 10, 22, 35, 12, 78, 41, 88, 48, 100, 34, 53, 27, 112, 126, 65, 136, 138, 148, 50, 78, 162, 83, 172, 89, 45, 95, 16, 196, 198, 210, 222, 113, 57, 232, 119, 120, 125, 256, 131, 268, 30, 69, 280, 282, 292, 34
EXAMPLE
The 3rd prime is 5 and mod 5, 3^4 = 1, so a(3) = 4.
MATHEMATICA
Table[With[{p=Prime[n]}, If[p==3, 0, MultiplicativeOrder[3, p]]], {n, 63}] (* Ray Chandler, Apr 06 2016 *)
PROG
(GAP) A000040:=Filtered([1..350], IsPrime);; (Python)
from sympy import n_order, prime
(PARI) a(n, {base=3}) = my(p=prime(n)); if(base%p, znorder(Mod(base, p)), 0) \\ Jianing Song, May 13 2024
CROSSREFS
Cf. A019334 (full reptend primes in base 3).
Order of 5 mod n-th prime: least k such that prime(n) divides 5^k-1.
+10
16
1, 2, 0, 6, 5, 4, 16, 9, 22, 14, 3, 36, 20, 42, 46, 52, 29, 30, 22, 5, 72, 39, 82, 44, 96, 25, 102, 106, 27, 112, 42, 65, 136, 69, 37, 75, 156, 54, 166, 172, 89, 15, 19, 192, 196, 33, 35, 222, 226, 114, 232, 119, 40, 25, 256, 262, 67, 27, 276, 140, 282, 292
MATHEMATICA
nn = 5; Table[If[Mod[nn, p] == 0, 0, MultiplicativeOrder[nn, p]], {p, Prime[Range[100]]}]
PROG
(GAP) A000040:=Filtered([1..350], IsPrime);; (PARI) a(n, {base=5}) = my(p=prime(n)); if(base%p, znorder(Mod(base, p)), 0) \\ Jianing Song, May 13 2024
CROSSREFS
Cf. A019335 (full reptend primes in base 5).
Odd primes with one coach: primes p such that A135303((p-1)/2) = 1.
+10
15
3, 5, 7, 11, 13, 19, 23, 29, 37, 47, 53, 59, 61, 67, 71, 79, 83, 101, 103, 107, 131, 139, 149, 163, 167, 173, 179, 181, 191, 197, 199, 211, 227, 239, 263, 269, 271, 293, 311, 317, 347, 349, 359, 367, 373, 379, 383, 389, 419, 421, 443, 461, 463, 467, 479, 487
COMMENTS
Given that prime p has only one coach, the corresponding value of k in A003558 must be (p-1)/2, and vice versa. Using the Coach theorem of Jean Pedersen et al., phi(b) = 2 * c * k, with b odd. Let b = p, prime. Then phi(p) = (p-1), and k must be (p-1)/2 iff c = 1. Or, phi(p) = (p-1) = 2 * 1 * (p-1)/2. Conjecture relating to odd integers: iff an integer is in the set A216371 and is either of the form 4q - 1 or 4q + 1, (q>0); then the top row of its coach (cf. A003558) is composed of a permutation of the first q odd integers. Examples: 11 is of the form 4q - 1, q = 3; with the top row of its coach [1, 5, 3]. 13 is of the form 4q + 1, q = 3; so has a coach of [1, 3, 5]. 37 is of the form 4q + 1, q = 9; so has a coach with the top row composed of a permutation of the first 9 odd integers: [1, 9, 7, 15, 11, 13, 3, 17, 5]. - Gary W. Adamson, Sep 08 2012 Odd primes p such that 2^m is not congruent to 1 or -1 (mod p) for 0 < m < (p-1)/2. - Charles R Greathouse IV, Sep 15 2012 These are also the odd primes a(n) for which there is only one periodic Schick sequence (see the reference, and also the Brändli and Beyne link, eq. (2) for the recurrence but using various inputs. See also a comment in A332439). This sequence has primitive period length (named pes in Schick's book) A003558((a(n)-1)/2) = A005034(a(n)) = A000010(a(n))/2 = (a(n) - 1)/2, for n >= 1. - Wolfdieter Lang, Apr 09 2020 Primes p such that the multiplicative order of 4 modulo p is (p-1)/2. Proof of equivalence: let ord(a,k) be the multiplicative of a modulo k.
If 2^m is not 1 or -1 (mod p) for 0 < m < (p-1)/2, then ord(2,p) is either p-1 or (p-1)/2. If ord(2,p) = p-1, then ord(4,p) = (p-1)/2. If ord(2,p) = (p-1)/2, then p == 3 (mod 4), otherwise 2^((p-1)/4) == -1 (mod p), so ord(4,p) = (p-1)/2.
Conversely, if ord(4,p) = (p-1)/2, then ord(2,p) = p-1, or ord(2,p) = (p-1)/2 and p == 3 (mod 4) (otherwise ord(4,p) = (p-1)/4). In the first case, (p-1)/2 is the smallest m > 0 such that 2^m == +-1 (mod p); in the second case, since (p-1)/2 is odd, 2^m == -1 (mod p) has no solution. In either case, so 2^m is not 1 or -1 (mod p) for 0 < m < (p-1)/2.
{(a(n)-1)/2} is the sequence of indices of fixed points of A053447. A prime p is a term if and only if one of the two following conditions holds: (a) 2 is a primitive root modulo p; (b) p == 3 (mod 4), and the multiplicative order of 2 modulo p is (p-1)/2 (in this case, we have p == 7 (mod 8) since 2 is a quadratic residue modulo p). (End)
Primes p such that 2 or -2 (or both) is a primitive root modulo p. Proof of equivalence: if ord(2,p) = p-1, then clearly ord(4,p) = (p-1)/2. If ord(-2,p) = p-1, then we also have ord(4,p) = (p-1)/2. Conversely, suppose that ord(4,p) = (p-1)/2, then ord(2,p) = p-1 or (p-1)/2, and ord(-2,p) = p-1 or (p-1)/2. If ord(2,p) = ord(-2,p) = (p-1)/2, then we have that (p-1)/2 is odd and (-1)^((p-1)/2) == 1 (mod p), a contradiction.
A prime p is a term if and only if one of the two following conditions holds: (a) -2 is a primitive root modulo p; (b) p == 3 (mod 4), and the multiplicative order of -2 modulo p is (p-1)/2 (in this case, we have p == 3 (mod 8) since -2 is a quadratic residue modulo p). (End)
No terms are congruent to 1 modulo 8, since otherwise we would have 4^((p-1)/4) = (+-2)^((p-1)/2) == 1 (mod p). - Jianing Song, May 14 2024
REFERENCES
P. Hilton and J. Pedersen, A Mathematical Tapestry, Demonstrating the Beautiful Unity of Mathematics, 2010, Cambridge University Press, pages 260-264.
Carl Schick, Trigonometrie und unterhaltsame Zahlentheorie, Bokos Druck, Zürich, 2003 (ISBN 3-9522917-0-6). Tables 3.1 to 3.10, for odd p = 3..113 (with gaps), pp. 158-166.
EXAMPLE
Prime 23 has a k value of 11 = (23 - 1)/2 (Cf. A003558(11). It follows that 23 has only one coach ( A135303(11) = 1). 23 is thus in the set. On the other hand 31 is not in the set since A135303(15) shows 3 coaches, with A003558(15) = 5. 13 is in the set since A135303(6) = 1; but 17 isn't since A135303(8) = 2.
MAPLE
isA216371 := proc(n)
if isprime(n) then
true;
else
false;
end if;
else
false;
end if;
end proc:
local p;
if n = 1 then
3;
else
p := nextprime(procname(n-1)) ;
while true do
if isA216371(p) then
return p;
end if;
p := nextprime(p) ;
end do:
end if;
end proc:
MATHEMATICA
Suborder[a_, n_] := If[n > 1 && GCD[a, n] == 1, Min[MultiplicativeOrder[a, n, {-1, 1}]], 0]; nn = 150; Select[Prime[Range[2, nn]], EulerPhi[#]/(2*Suborder[2, #]) == 1 &] (* T. D. Noe, Sep 18 2012 *) f[p_] := Sum[Cos[2^n Pi/((2 p + 1))], {n, p}]; 1 + 2 * Select[Range[500], Reduce[f[#] == -1/2, Rationals] &]; (* Gerry Martens, May 01 2016 *)
PROG
(PARI) is(p)=for(m=1, p\2-1, if(abs(centerlift(Mod(2, p)^m))==1, return(0))); p>2 && isprime(p) \\ Charles R Greathouse IV, Sep 18 2012 (PARI) is(p) = isprime(p) && (p>2) && znorder(Mod(4, p)) == (p-1)/2 \\ Jianing Song, Dec 24 2022
CROSSREFS
A105876 is the subsequence of terms congruent to 3 modulo 4.
Complement of A268923 in the set of odd primes.
Order of 9 mod n-th prime: least k such that prime(n) divides 9^k-1.
+10
13
1, 0, 2, 3, 5, 3, 8, 9, 11, 14, 15, 9, 4, 21, 23, 26, 29, 5, 11, 35, 6, 39, 41, 44, 24, 50, 17, 53, 27, 56, 63, 65, 68, 69, 74, 25, 39, 81, 83, 86, 89, 45, 95, 8, 98, 99, 105, 111, 113, 57, 116, 119, 60, 125, 128, 131, 134, 15, 69, 140, 141, 146, 17, 155, 39
FORMULA
a(n) <= (prime(n) - 1)/2. Those prime(n) for which a(n) = (prime(n) - 1)/2 are listed in A364867. (End)
MATHEMATICA
nn = 9; Table[If[Mod[nn, p] == 0, 0, MultiplicativeOrder[nn, p]], {p, Prime[Range[100]]}]
PROG
(GAP) A000040:=Filtered([1..350], IsPrime);; (PARI) a(n, {base=9}) = my(p=prime(n)); if(base%p, znorder(Mod(base, p)), 0) \\ Jianing Song, May 13 2024
Order of 6 mod n-th prime: least k such that prime(n) divides 6^k-1.
+10
12
0, 0, 1, 2, 10, 12, 16, 9, 11, 14, 6, 4, 40, 3, 23, 26, 58, 60, 33, 35, 36, 78, 82, 88, 12, 10, 102, 106, 108, 112, 126, 130, 136, 23, 37, 150, 156, 27, 83, 43, 178, 60, 19, 96, 14, 198, 105, 222, 226, 228, 232, 17, 20, 250, 256, 131, 134, 270, 276, 56, 141
MAPLE
if n<= 2 then
0 ;
else
numtheory[order](6, ithprime(n)) ;
end if;
end proc:
MATHEMATICA
nn = 6; Table[If[Mod[nn, p] == 0, 0, MultiplicativeOrder[nn, p]], {p, Prime[Range[100]]}]
PROG
(GAP) A000040:=Filtered([1..350], IsPrime);; (PARI) a(n, {base=6}) = my(p=prime(n)); if(base%p, znorder(Mod(base, p)), 0) \\ Jianing Song, May 13 2024
CROSSREFS
Cf. A019336 (full reptend primes in base 6).
Order of 7 mod n-th prime: least k such that prime(n) divides 7^k-1.
+10
12
1, 1, 4, 0, 10, 12, 16, 3, 22, 7, 15, 9, 40, 6, 23, 26, 29, 60, 66, 70, 24, 78, 41, 88, 96, 100, 51, 106, 27, 14, 126, 65, 68, 69, 74, 150, 52, 162, 83, 172, 178, 12, 10, 24, 98, 99, 210, 37, 113, 228, 116, 238, 240, 125, 256, 262, 268, 135, 138, 20, 141, 292
MATHEMATICA
nn = 7; Table[If[Mod[nn, p] == 0, 0, MultiplicativeOrder[nn, p]], {p, Prime[Range[100]]}]
PROG
(GAP) A000040:=Filtered([1..350], IsPrime);; (PARI) a(n, {base=7}) = my(p=prime(n)); if(base%p, znorder(Mod(base, p)), 0) \\ Jianing Song, May 13 2024
CROSSREFS
Cf. A019337 (full reptend primes in base 7).
Order of 8 mod n-th prime: least k such that prime(n) divides 8^k-1.
+10
12
0, 2, 4, 1, 10, 4, 8, 6, 11, 28, 5, 12, 20, 14, 23, 52, 58, 20, 22, 35, 3, 13, 82, 11, 16, 100, 17, 106, 12, 28, 7, 130, 68, 46, 148, 5, 52, 54, 83, 172, 178, 60, 95, 32, 196, 33, 70, 37, 226, 76, 29, 119, 8, 50, 16, 131, 268, 45, 92, 70, 94, 292, 34, 155, 52
MATHEMATICA
nn = 8; Table[If[Mod[nn, p] == 0, 0, MultiplicativeOrder[nn, p]], {p, Prime[Range[100]]}]
PROG
(GAP) A000040:=Filtered([1..350], IsPrime);; (PARI) a(n, {base=8}) = my(p=prime(n)); if(base%p, znorder(Mod(base, p)), 0) \\ Jianing Song, May 13 2024
CROSSREFS
Cf. A053451 (order of 8 mod 2n+1), A019338 (full reptend primes in base 8).
Order of 16 modulo the n-th prime: least k such that prime(n) divides 16^k-1.
+10
5
1, 1, 3, 5, 3, 2, 9, 11, 7, 5, 9, 5, 7, 23, 13, 29, 15, 33, 35, 9, 39, 41, 11, 12, 25, 51, 53, 9, 7, 7, 65, 17, 69, 37, 15, 13, 81, 83, 43, 89, 45, 95, 24, 49, 99, 105, 37, 113, 19, 29, 119, 6, 25, 4, 131, 67, 135, 23, 35, 47, 73, 51, 155, 39, 79, 15, 21, 173, 87, 22, 179
COMMENTS
a(n) is the period of the expansion of 1/prime(n) in hexadecimal.
FORMULA
a(n) <= (prime(n) - 1)/2.
PROG
(PARI) a(n) = znorder(Mod(16, prime(n))).
CROSSREFS
Cf. A302141 (order of 16 mod 2n+1).
For p = prime(n), a(n) is the smallest N such that pN is a base-2 pseudoprime (that is, 2^(pN-1) = 1 mod pN).
+10
3
187, 129, 247, 31, 85, 33, 73, 89, 85, 11, 73, 161, 15, 93, 157, 233, 481, 133, 281, 19, 391, 1067, 23, 193, 601, 307, 6361, 37, 29, 15, 2731, 545, 10213, 593, 31, 53, 2593, 499, 1205, 141155, 1261, 2281, 97, 3333, 1387, 1891, 1777, 3391, 381, 59, 20231, 97
COMMENTS
Tables compiled by Pinch were used. Sequence A085999 lists a(n)*prime(n). It can be shown that a(n) has the form 1 + 2 ord(4, prime(n)) k for some k > 0, where the ord(x,y) function is the smallest positive integer r such that x^r = 1 mod y. The value of k for a(n) is given in sequence A086001. Note that prime(n) divides 2^a(n) - 2. Compare A085012, which gives the smallest prime q such that pq is a 2-pseudoprime.
EXAMPLE
a(2) = 187 because prime(2) = 3 and N=187 is the smallest number such that 3N is a 2-pseudoprime.
MATHEMATICA
Table[p=Prime[n]; m=MultiplicativeOrder[4, p]; k=1; While[psp=p(1+2*m*k); PowerMod[2, psp-1, psp]!=1, k++ ]; 1+2*m*k, {n, 2, 100}]
Search completed in 0.012 seconds
| 