In the first part of the paper we study arithmetical properties of Pascal triangles modulo a prime power; the main result is the generalization of Lucas' theorem. Then we investigate the structure N; Bpx, where p is a prime, α is an integer greater than one, and Bpx = Rem, px); it is shown that addition is first-order definable in this structure, and that its elementary theory is decidable.

Let $ be the restriction of usual order relation to integers which are primes or squares of primes, and let ⊥ denote the coprimeness predicate. The elementary theory of $\langle\mathbb{N};\bot, , is undecidable. Now denote by $ the restriction of order to primary numbers. All arithmetical relations restricted to primary numbers are definable in the structure $\langle\mathbb{N};\bot, . Furthermore, the structures $\langle\mathbb{N};\mid, and $\langle\mathbb{N};=,+,x\rangle$ are interdefinable.

Rationals and countable ordinals are important examples of structures with decidable monadic second-order theories. A chain is an expansion of a linear order by monadic predicates. We show that if the monadic second-order theory of a countable chain C is decidable then C has a non-trivial expansion with decidable monadic second-order theory.

Letkandlbe two multiplicatively independent integers, and letL⊆ ℕnbe al-recognizable set which is not definable in 〈ℕ; +〉. We prove that the elementary theory of 〈ℕ; +,Vk, L〉, whereVk(x)denotes the greatest power ofkdividingx, is undecidable. This result leads to a new proof of the Cobham-Semënov theorem.