×

On Pascal triangles modulo a prime power. (English) Zbl 0889.11008

For every integer \(n\geq 1\), the Pascal triangle modulo \(n\) is the binary function \(B_n\) on \(\mathbb{N}^2\) defined by \[ B_n(x,y) =\text{Rem} \left( {x+y \choose x},n \right), \] where \(\text{Rem}(a,b)\) denotes the remainder by integer division of \(a\) by \(b\), and ( ) is the binomial coefficient. In the first part of this paper, the author studies arithmetical properties of Pascal triangles modulo a prime power; the main result is the generalization of Lucas’ theorem. Then he investigates the structure \(\langle \mathbb{N}; B_{p^\alpha} \rangle\), where \(p\) is a prime and \(\alpha\) is an integer greater than one. It is also shown that addition is first-order definable in this structure, and that its elementary theory is decidable.

MSC:

11B65 Binomial coefficients; factorials; \(q\)-identities
03B25 Decidability of theories and sets of sentences
11U05 Decidability (number-theoretic aspects)
03F30 First-order arithmetic and fragments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bailey, D. F., Two \(p^3\) variations of Lucas theorem, J. Number Theory, 35, 2, 208-215 (1990) · Zbl 0704.11001
[2] Bruyère, V.; Hansel, G.; Michaux, C.; Villemaire, R., Logic and \(p\)-recognizable sets of integers, Bull. Belg. Math. Soc., 1, 191-238 (1994) · Zbl 0804.11024
[3] Büchi, J. R., Weak second-order arithmetic and finite automata, Zeitschrift für Math. Logic Grun- dlagen Math., 6, 66-92 (1960) · Zbl 0103.24705
[4] Davis, K.; Webb, W., A binomial coefficient congruence modulo prime powers, J. Number Theory, 43, 1, 20-23 (1993) · Zbl 0769.11008
[5] Hodgson, B. R., Décidabilité par automate fini, Ann. Sci. Math. Québec, 7, 39-57 (1983) · Zbl 0531.03007
[6] Korec, I., Definability of arithmetic operations in Pascal triangle modulo an integer divisible by two primes, Grazer Matematische Berichte, 318, 53-62 (1993) · Zbl 0797.11024
[7] Korec, I., Structures related to Pascal’s triangle modulo 2 and their elementary theories, Math. Slovaca, 44, 5, 531-554 (1994) · Zbl 0824.11008
[8] Korec, I., Elementary theories of structures containing generalized Pascal triangles modulo a prime, (Shtrakov, S.; Mirchev, Iv., Proc. 5th Conf. on Discrete Mathematics and Applications (1995), Blagoevgrad/Predel: Blagoevgrad/Predel Blagoevgrad), 91-102
[9] Korec, I., Theories of generalized Pascal triangles, (Proc. Logic Colloquium’94. Proc. Logic Colloquium’94, Ann. Pure Appl. Logic, 89 (1997)), 45-52 · Zbl 0889.11009
[10] Lucas, E., Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques, suivant un module premier, Bull. Soc. Math. France, 6, 49-54 (1878) · JFM 10.0139.04
[11] McIntosh, R., A generalization of congruential property of Lucas, Amer. Math. Monthly, 99, 3, 231-238 (1992) · Zbl 0755.11001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.