\(\sc{RELATIVE}\ \sc{PRIMALITY}\) can be solved by applying Euclid’s greatest common divisor algorithm – i.e. on input \(y \leq x\), repeatedly compute the remainders \(r_0 = \text{rem}(x,y)\), \(r_1 = \text{rem}(y, r_0)\), \(r_2 = \text{rem}(r_0, r_1)\) …, until \(r_i = 0\) and then return ‘yes’ if \(r_{i-1} = 1\) and ‘no’ otherwise. It may be shown that the number of steps in this sequence is always less than or equal to   \(5 \cdot \log_{10}(x)\).[2]   This means that in order to determine if \(x\) and \(y\) are relatively prime, it suffices to calculate a number of remainders which is proportional to the number of digits in the decimal representation of the smaller of the two numbers. As this may also be accomplished by an efficient algorithm (e.g. long division), it may plausibly be maintained that if we are capable of inscribing a pair of numbers \(x,y\) – e.g. by writing their numerical representations in binary or decimal notation on a blackboard or by storing such numerals in the memory of a digital computer of current design – then either we or such a computer will also be able to carry out these algorithms in order to decide whether \(x\) and \(y\) are relatively prime. This is the hallmark of a feasibly decidable problem – i.e. one which can be decided in the ‘in practice’ sense of everyday concretely embodied computation.