-1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ What about $k=b$, $n=a^b-b$? $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Nov 11, 2017 at 12:52
  • $\begingroup$ You are right - see also the answer below $\endgroup$
    – Dominic van der Zypen
    Commented Nov 11, 2017 at 13:45

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Note that taking some prime factor of $n$ we may even assume that $n$ is prime. $\endgroup$
    – Wojowu
    Commented Nov 10, 2017 at 10:04
  • $\begingroup$ @Wojowu:That is much less obvious to achieve because of the condition $n > a,b$. $\endgroup$
    – js21
    Commented Nov 10, 2017 at 10:15
  • $\begingroup$ ah, right, I've missed that. It should still be true that $n$ may be taken prime, but a separate argument for that would be necessary. $\endgroup$
    – Wojowu
    Commented Nov 10, 2017 at 10:18

Not the answer you're looking for? Browse other questions tagged .