The Euclidean algorithm computes the greatest common divisor of two numbers a, b and decides whether they are coprime using no more than $2\log(\min(a,b))$ divisions and no other operations. It is not known whether it is optimal, and the question is apparently quite difficult. Part of my aim in this talk is to formulate, explain and justify a general postulate about algorithms from specified primitives (like the Euclidean), which makes it possible in some cases to derive lower complexity bounds that apply to all algorithms that decide a specific relation from specified primitives. This Embedding Principle is different in form but has the same intent for complexity as that of the classical Church-Turing Thesis for computability, which is used to establish absolute undecidability results. I will also discuss several specific lower bound results obtained by this method, for arithmetical relations like coprimeness, being a perfect square or square-free, etc., from various primitives. This work is joint with Lou van den Dries.