login
Irregular triangle read by rows: row n gives the members of the smallest nonnegative reduced residue system in the modified congruence modulo n by Brändli and Beyne, called mod* n.
4

%I #16 Feb 27 2024 07:36:44

%S 0,1,1,1,1,2,1,1,2,3,1,3,1,2,4,1,3,1,2,3,4,5,1,5,1,2,3,4,5,6,1,3,5,1,

%T 2,4,7,1,3,5,7,1,2,3,4,5,6,7,8,1,5,7,1,2,3,4,5,6,7,8,9,1,3,7,9,1,2,4,

%U 5,8,10,1,3,5,7,9,1,2,3,4,5,6,7,8,9,10,11

%N Irregular triangle read by rows: row n gives the members of the smallest nonnegative reduced residue system in the modified congruence modulo n by Brändli and Beyne, called mod* n.

%C The length of row n is A023022(n), for n >= 1, with A023022(1) = 1.

%C See the Brändli-Beyne link for this mod* system.

%C This reduced residue system mod* n will be called RRS*(n). The mod* n system is defined only for numbers coprime to n. The definition of mod*(a, n), for gcd(a, n) = 1, is mod(a, n) from RRS(n) given in A038566, if mod(a, n) <= floor(n/2) and mod(-a, n) from RRS(n) otherwise. E.g., mod*(17, 10) = mod(-17, 10) = 3 because mod(17, 10) = 7 > 10/2 = 5. mod*(22, 10) is not defined because gcd(22, 10) = 2, not 1.

%C Compare this table with the one for the reduced residue system modulo n (called RRS(n)) from A038566. For n >= 3 RRS*(n) consists of the first half of the RRS(n) members.

%C Each member j of RRS*(n) stands for a reduced representative class [j]* which is given by the union of the ordinary reduced representative classes [j] and [n-j] modulo n, for n >= 3, with j from the first half of the set RRS(n) given in row n of A038566 (but with 0 for n = 1). For n = 1: [0]* = [0] (using A038566(1) = 0, not 1), representing all integers. For n = 2: [1]* = [1], representing all odd integers.

%C E.g., RRS*(5) = {1, 2} (always considered ordered), and [1]* = {pm1, pm4, pm5, pm9, ...} (pm for + or -), and [2]* = {pm2, pm3, pm7, pm8, ...}. Hence RRS*(5) represents the same integers as RRS(5), but has only 2, not 4 elements (RRS*(5) is not equal to RRS(5)).

%C The modular arithmetic is multiplicative but not additive for mod* n. This is based on the fact that gcd(a*b, n) = 1 if gcd(a, n) = 1 = gcd(b, n) (not valid in general for gcd(a + b, n)). E.g., 2 = mod*(92, 9) = mod*(23*4, 9) = mod*(4*4, 10) = 2, because 2 <= 4, 5 > 4, 4 <= 4, 7 > 4, hence mod*(23, 9) = mod(-23, 9) = 4, mod*(4, 9) = 4 and mod*(16, 9) = mod(-16, 9) = 2. For n = 9 the class [2]* consists of [2] union [9-2], i.e, {pm2, pm7, pm11, pm16, ...}.

%H Gerold Brändli and Tim Beyne, <a href="https://arxiv.org/abs/1504.02757">Modified Congruence Modulo n with Half the Amount of Residues</a>, arXiv:1504.02757 [math.NT], 2016.

%F T(1, 1) = 0, T(2, 1) = 1, and T(n, k) = A038566(n, k) for k = 1, 2, ..., A023022(n), for n >= 3.

%e The irregular triangle T(n, k) begins:

%e n\k 1 2 3 4 5 6 7 8 9 ...

%e -----------------------------------------

%e 1: 0

%e 2: 1

%e 3: 1

%e 4: 1

%e 5: 1 2

%e 6: 1

%e 7: 1 2 3

%e 8: 1 3

%e 9: 1 2 4

%e 10: 1 3

%e 11: 1 2 3 4 5

%e 12: 1 5

%e 13: 1 2 3 4 5 6

%e 14: 1 3 5

%e 15: 1 2 4 7

%e 16: 1 3 5 7

%e 17: 1 2 3 4 5 6 7 8

%e 18: 1 5 7

%e 19: 1 2 3 4 5 6 7 8 9

%e 20: 1 3 7 9

%e ...

%e -----------------------------------------

%e n = 9: 1 represents the union of the ordinary restricted residue classes [1] and [-1] = [8], called [1]*, 2 represents the union of [2] and [-2] = [7], called [2]*, and 4 represents the union of [4] and [-4] = [5], called [4]*. One could replace [1]* by [8]*, [2]* by [7]* and [4]* by [5]*, but here the smallest numbers 1, 2, 4 are used for RRS*(9).

%e Multiplication table for RRS*(9) (x is used here instead of *): 1 x 1 = 1, 1 x 2 = 2, 1 x 4 = 4; 2 x 1 = 2, 2 x 2 = 4, 2 x 4 = 1; 4 x 1 = 4, 4 x 2 = 1, 4 x 4 = 2. This is the (Abelian) cyclic group C_3.

%o (PARI) RRS(n) = select(x->gcd(n, x)==1, [1..n]); \\ A038566

%o row(n) = if (n<=2, [n-1], my(r=RRS(n)); Vec(r, #r/2)); \\ _Michel Marcus_, Sep 17 2023

%Y Cf. A023022, A038566 (RRS), A333857.

%Y Essentially the same as A182972.

%K nonn,tabf,easy

%O 1,6

%A _Wolfdieter Lang_, Jun 26 2020