Informally speaking, I was wondering whether the relation 



> 
> $a^k \equiv b \text{ (mod } n)$ for some $k,n$
> 
> 
> 


is computable. More formally: Let $\mathbb{N}$ denote the set of the positive integers and set $$R = \big\{(a,b)\in \mathbb{N}\times\mathbb{N}:(\exists k,n \in\mathbb{N}): (n>\max\{a,b\})\land (a^k \equiv b \text{ (mod } n))\big\}.$$ Is $R$ computable?



Computability of a relation connected to the discrete logarithm
Of course since $R = \{ (a,b) \in \mathbb{N} \times \mathbb{N} \ | \ (a=1) \implies (b=1) \} $.
Indeed for $a > 1$ one can take $n = a^k-b$ for $k$ large enough.


