login
Cardinality of the shortcut set of the multiplicative group of integers modulo the n-th primorial.
1

%I #73 Jul 29 2019 12:20:15

%S 1,2,4,48,384,2304,4608,18432,552960,19906560,796262400,33443020800,

%T 66886041600,267544166400,535088332800,32105299968000,

%U 2118949797888000,148326485852160000,10679506981355520000,833001544545730560000,1666003089091461120000,146608271840048578560000

%N Cardinality of the shortcut set of the multiplicative group of integers modulo the n-th primorial.

%C {R(1),...,R(phi(prime(n)#))} = {(prime(n)#/2 +- {R(1),...,R(k)}*2^{1,2,...,z}) mod prime(n)#}.

%C The formula is used for the compressed representation of the set of the multiplicative group of integers modulo prime(n)#. This is a new formula in number theory. {R(1),...,R(k)} is the shortcut set of the multiplicative group of integers modulo prime(n)# (or compressed representation of the set of the multiplicative group of integers modulo prime(n)#).

%H Alexey V. Bazhin, <a href="/A308665/b308665.txt">Table of n, a(n) for n = 3..24</a>

%F a(n) = A005867(n+2)/(2*A155747(n+1)).

%F If {R(1),...,R(phi(prime(n)#))} = {(prime(n)#/2 +- {R(1),...,R(k)}*2^{1,2,...,z}) mod prime(n)#} then a(n) = k.

%e First example:

%e Let R = {1, 7, 11, 13, 17, 19, 23, 29} be the set of the multiplicative group of integers modulo 30 (or it is the set of positive integers less than 2*3*5 and prime to 2*3*5, or it is the reduced residue system for the 3rd primorial number 30 = A002110(3)).

%e The cardinality of |R| is equal to 8 elements, 8 = A005867(3).

%e The set {1} is the shortcut set of the multiplicative group of integers modulo 30.

%e The cardinality of |{1}| = 1, i.e., a(1) = 1.

%e R = { (30/2 +- {1}*2^{1, ..., 4}) mod 30 } = {(30/2 +- {1}*2^{1,2,3,4}) mod 30}={(15+2^1) mod 30, (15-2^1) mod 30,(15+2^2) mod 30, (15-2^2) mod 30, (15+2^3) mod 30, (15-2^3) mod 30, (15+2^4) mod 30, (15-2^4) mod 30} = {1,7,11,13,17,19,23,29},

%e where 30 = A002110(3), 4 = A155747(2), |R| = A005867(3).

%e 4 is the smallest number m with the property that 2^m-1 is divisible by the first n odd primes.

%e Second example:

%e Let R = {1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209} be the set of the multiplicative group of integers modulo 210 (or it is the set of positive integers less than 2*3*5*7 and prime to 2*3*5*7, or it is the reduced residue system for the 4th primorial number 210 = A002110(4)).

%e The cardinality of |R| is equal to 48 elements, 48 = A005867(5).

%e The set {1, 11} is the shortcut set of the multiplicative group of integers modulo 210.

%e The cardinality of |{1, 11}| = 2, i.e., a(2) = 2.

%e R = { ( 210/2 +- {1, 11}*2 ^{1..12}) mod 210 }, where 210 = A002110(4), 12 = A155747(3), |R| = A005867(4).

%e 12 is the smallest number m with the property that 2^m-1 is divisible by the first n odd primes.

%e General case:

%e R = {R(1), ..., R(phi(prime(n)#))},

%e R = {(prime(n)#/2 +- {R(1),R(2),...,R(k)}*2^{1,2,...,z}) mod prime(n)#}, where prime(n)# is the product of the first n primes, i.e., it is A002110(n); phi is Euler's totient function, which counts the positive integers up to a given argument that are relatively prime to the argument, in our case phi(prime(n)#) is A005867;

%e R is the set of the multiplicative group of integers modulo prime(n)#;

%e z is a term of A155747.

%e k is a term of a(n).

%e R(1) <= R(k) < R(phi(prime(n)#)).

%e Table:

%e +-----+-----------+----------------+---------+------+

%e | n | A002110 | A005867 | A155747 | a(n) |

%e | | prime(n)# | phi(prime(n)#) | z | k |

%e +-----+-----------+----------------+---------+------+

%e | 0 | 1 | 1 | - | - |

%e | 1 | 2 | 1 | - | - |

%e | 2 | 6 | 2 | 2 | - |

%e | 3 | 30 | 8 | 4 | 1 |

%e | 4 | 210 | 48 | 12 | 2 |

%e | 5 | 2310 | 480 | 60 | 4 |

%e | 6 | 30030 | 5760 | 60 | 48 |

%e | 7 | 510510 | 92160 | 120 | 384 |

%e | 8 | 9699690 | 1658880 | 360 | 2304 |

%e | .. | ... | ... | ... | ... |

%o (PARI) f(n) = prod(k=1, n, prime(k)-1); \\ A005867

%o g(n) = lcm(vector(n, k, znorder(Mod(2, prime(k+1))))); \\ A155747

%o a(n) = f(n+2)/(g(n+1)*2); \\ _Michel Marcus_, Jun 25 2019

%Y Cf. A000040, A002110, A005867, A155747.

%K nonn,easy

%O 3,2

%A _Alexey V. Bazhin_, Jun 15 2019