×

Definability of arithmetic operations in Pascal triangle modulo an integer divisible by two primes. (English) Zbl 0797.11024

Summary: We investigate the structures (\(\mathbb{N};B_ n)\), where \(B_ n(x,y) = {x+y \choose x}\) mod \(n\). Addition and multiplication on the set \(\mathbb{N}\) of nonnegative integers are first order definable in \((\mathbb{N};B_ n)\) provided \(n>0\) is divisible by two distinct primes. Consequently, the elementary theory of \((\mathbb{N};B_ n)\) is undecidable for such \(n\). On the other hand, the elementary theory of \((\mathbb{N};B_ 2)\) is shown to be decidable.

MSC:

11B75 Other combinatorial number theory
11U05 Decidability (number-theoretic aspects)
03B25 Decidability of theories and sets of sentences
PDFBibTeX XMLCite