1
$\begingroup$

Given positive integers $1< x,y < 2019$ that satisfy system of equations

$1992^{x} \ \ (mod \ 2019) = n$ and $n^{y} \ \ (mod \ 2019) = 1992$

Question :

(i) How many pairs of $(x,y)$ satisfy above condition?

(ii) Let $S=\left \{ x \right \}$ and $T = \left \{ y \right \}$ What is the sum of members in $S$ and $T$

I created this Question from reading an RSA encryption ,but fundamentally I solved this and got only $(5,269)$ for one solution ,there are so many pairs of $(x,y)$ that take time to find out .

Are there any quicker way solution to manage$(x,y)$ and find the sum of members in set $S$ and set $T$?

I appreciate for any helps, Thank you.

$\endgroup$
1
  • $\begingroup$ MathJax hint: to get the modulo like you want use \pmod {2019} so $1992^x \pmod {2019}$ $\endgroup$ Commented Jul 14, 2019 at 17:42

1 Answer 1

3
$\begingroup$

You are looking for solutions to $(1992^x)^y=1992^{xy}\equiv 1992 \pmod {2019}$

By Euler's theorem we have $a^{\varphi(2019)}\equiv 1 \pmod {2019}$ for any $a$ coprime to $2019$. $\varphi(2019)=1344$. The order of $1992 \mod 2019$ must be a factor of $1344$ and we can easily check that $1992^{672},$ $1992^{348},$and $1992^{192}$ are not $1$, so you need $xy\equiv 1 \pmod {1344}$. Any $x$ coprime to $1344$ will have an inverse, which will be the corresponding $y$. For example, we have $13^{-1}\equiv 517 \pmod {1344}$ and $1992^{13 \cdot 517}=1992^{6721}\equiv 1992 \pmod {2019}$ so $(13,517)$ is another pair.

$\endgroup$
4
  • $\begingroup$ Thank you , and what about question (ii) ? Should I find all pairs by hands or it has a formula to sum these coprime numbers? $\endgroup$ Commented Jul 14, 2019 at 19:40
  • 1
    $\begingroup$ You can just use inclusion-exclusion. The sum of all the numbers up to $1344$ is $\frac 12\cdot 1344 \cdot 1345$. The sum of the even numbers is ??? The sum of the ones that are multiples of $3$ is ??? If you subtract those you subtract the multiples of $6$ twice, so add them back in. Now deal with the sevens. $\endgroup$ Commented Jul 14, 2019 at 20:38
  • $\begingroup$ Thank you , I see through the problem just sum up all consecutive numbers from $2$ to $1343$ then subtract out even numbers , multiple of $3$ and the last one multiple of $7$ because $ 2^{6} \times 3 \times 7 = 1344 $ all of that is set $ \left \{ x \right \}$ but the problem is numbers in set $ \left \{ y \right \}$ we cannot see the pattern because it's construct from inverse of set $ \left \{ x \right \}$ and from multiple of $ \varphi \left ( 2019 \right )$ + member in set $ \left \{ x \right \}$ . How can we deal of it ? $\endgroup$ Commented Jul 14, 2019 at 22:32
  • $\begingroup$ The numbers in the set $\{y\}$ will be the same ones as in the set $\{x\}$, just in a scrambled order. The inverse relation is symmetric, so if $(x,y)$ is a solution, so is $(y,x)$ $\endgroup$ Commented Jul 14, 2019 at 23:01

You must log in to answer this question.

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