A215202 Irregular triangle in which n-th row gives m in 1, ..., n-1 such that m^2 == m (mod n).

1, 1, 1, 1, 1, 3, 4, 1, 1, 1, 1, 5, 6, 1, 1, 4, 9, 1, 1, 7, 8, 1, 6, 10, 1, 1, 1, 9, 10, 1, 1, 5, 16, 1, 7, 15, 1, 11, 12, 1, 1, 9, 16, 1, 1, 13, 14, 1, 1, 8, 21, 1, 1, 6, 10, 15, 16, 21, 25, 1, 1, 1, 12, 22, 1, 17, 18, 1, 15, 21, 1, 9, 28, 1, 1, 19, 20, 1, 13

Offset: 2

Author

Eric M. Schmidt, Aug 05 2012

Keywords

• nonn
• tabf

Comments

The n-th row has length A034444(n) - 1.

If m appears in row n, then gcd(n,m) appears in the n-th row of A077610. Moreover, if m', distinct from m, also appears in row n, then gcd(n, m) does not equal gcd(n, m').

For odd n and any integer m, m^2 == m (mod n) iff m^2 == m (mod 2n).

Let P(1)={1} and for integers x > 1, let P(x) be the set of distinct prime divisors of x. We can define an equivalence relation ~ on the set of elements in the ring (Z_n, +mod n,*mod n): for all a,b in Z_n (where a,b are the least nonnegative residues modulo n) a ~ b iff P(gcd(a,n)) intersect P(n) is equal to P(gcd(b,n)) intersect P(n). If we include 0 in each row then these elements can represent the equivalence classes. They form a commutative monoid. - Geoffrey Critzer, Feb 13 2016

Examples

			Triangle begins:
1;
1;
1;
1;
1, 3, 4;
1;
1;
1;
1, 5, 6;
1;
1, 4, 9;
1;
1, 7, 8;
1, 6, 10;
1;
1;
1, 9, 10; etc.  - _Bruno Berselli_, Aug 06 2012
		

Links

• Eric M. Schmidt, Rows 2..2000, flattened

Crossrefs

For m^2 == m (mod n), see: n=2: A001477; n=3: A032766; n=4: A042948; n=5: A008851; n=6: A032766; n=7: A047274; n=8: A047393; n=9: A090570; n=10: A008851; n=11: A112651; n=12: A112652; n=13: A112653; n=14: A047274; n=15: A151972; n=16: A151977; n=17: A151978; n=18: A090570; n=19: A151979; n=20: A151980; n=21: A151971; n=22: A112651; n=24: A151973; n=26: A112653; n=30: A151972; n=32: A151983; n=34: A151978; n=38: A151979; n=42: A151971; n=48: A151981; n=64: A151984; n=100: A008852; n=1000: A008853.

Programs

Magma

[m: m in [1..n-1], n in [2..40] | m^2 mod n eq m]; // Bruno Berselli, Aug 06 2012

Mathematica

Table[Select[Range[n], Mod[#^2, n] == # &], {n, 2, 30}] // Grid (* Geoffrey Critzer, May 26 2015 *)

Sage

def A215202(n) : return [m for m in range(1, n) if m^2 % n == m];