0
$\begingroup$

Is it possible, for $a,b,m,n,x,y\in\mathbb N$ to have

$$x = y^a \pmod n \qquad \text{ and }\qquad y = x^b \pmod m ?$$

For example: $17=5^{11} \pmod{21}$ and $5=17^{11} \pmod{21}$ is an integer but i want to use different value of modulo in both equation instead of using $21$.

$\endgroup$
10
  • 2
    $\begingroup$ You mean like $2 = 3^2 \bmod 7$ and $3 = 2^3 \bmod 5$? Sure it's possible $\endgroup$
    – Cocopuffs
    Jul 10, 2013 at 19:18
  • $\begingroup$ yes but how can u explain it? $\endgroup$
    – Aria
    Jul 10, 2013 at 19:20
  • $\begingroup$ $2$ is a primitve root modulo $5$ and $3$ is a primitive root modulo $7$ so we were guaranteed to find something... $\endgroup$
    – Cocopuffs
    Jul 10, 2013 at 19:21
  • $\begingroup$ Do you want $a=b$ in your statement? At least $a=b=11$ in the example. $\endgroup$ Jul 10, 2013 at 19:21
  • $\begingroup$ no not necessary that a=b. $\endgroup$
    – Aria
    Jul 10, 2013 at 19:22

1 Answer 1

1
$\begingroup$

Take any two powers $y^a$ and $x^b$. Then let $n$ be any divisor of $y^a-x$ and $m$ be any divisor of $x^b-y$.

For instance, consider $y^a=3^5$ and $x^b=7^{11}$. Now factor $3^5-7$ and $7^{11}-3$: $$3^5-7=2^2 \cdot 59, \text{ and } 7^{11}-3=2^2 \cdot 5\cdot 98866337.$$ Then, for example, you can take $n=59$, and $m=98866337$.

$\endgroup$
3
  • $\begingroup$ how do u find the value of $n$=59 and $m$=98866337. $\endgroup$
    – Aria
    Jul 10, 2013 at 19:34
  • $\begingroup$ By factoring $y^a-x$ and $x^b-y$. I updated the answer. $\endgroup$ Jul 10, 2013 at 19:37
  • $\begingroup$ Is it possible if we only know the value of x,n,a? i mean we have all parameter of first equation except y and have to calculate y by help of x,a,n and then value of m. $\endgroup$
    – Aria
    Jul 10, 2013 at 19:45

You must log in to answer this question.

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