2

How many positive a,b pair solutions are there for the formula below and is there an easy way to find them all?

$$a * b \equiv 1 \pmod{n}$$

Where $a,b,n \in \mathbb{Z}$ and $0 < a \leq b < n$

Ilya Gazman
  • 1,440
  • 6
    See Euler's totient function. A given integer $a$ has a multiplicative inverse modulo $n$ if and only if $\gcd(a,n) = 1$, and Euler's totient function measures how many integers $a \in {1,\ldots,n-1}$ are coprime with $n$. Since you're looking at (presumably ordered) pairs, you need to give some care to the case where $a \equiv a^{-1} \mod n$, e.g., $a=2$, $n=3$. – Hayden Jul 14 '20 at 22:14
  • 1
    In order for the congruence to have a solution, both $a,b$ must individually be relatively prime with $n$, so the number of $a$ matching this criteria is $\varphi(n)$. If there are two different $b$ which each solve the modular equivalence for a given $n$, then there is a zero divisor, so there must be a unique $b$ for each given $a$. Can you conclude? – abiessu Jul 14 '20 at 22:17
  • based on "is there an easy way to find them all", it is unclear to me whether the following question is off-topic: given that a is relative prime to n and S is the set of all residues mod n that are relatively prime to n, is there an easy way of finding the unique element x in S such that $ax \equiv 1 \pmod{n}?$ To the best of my knowledge, the answer is no. – user2661923 Jul 14 '20 at 22:43
  • extending my previous comment, if $n$ is composite and equals the product of primes $p_1 \times p_2 \times \cdots \times p_r,$ and you are given $a$ and searching for $x$, then I would take the following approach. Manually compute the residue of $x \pmod{p_i} ;: 1 \leq i \leq r.$ Then apply number theory around the chinese remainder theorem. Of course this begs the complicating question: what if (for example) $(p_1)^2$ divides $n?$ – user2661923 Jul 14 '20 at 22:56
  • Tnx @Hayden, this is the solution I was looking for. Can you please just explain more what is special about $a=2 , n=3$ – Ilya Gazman Jul 14 '20 at 23:38
  • 2
    @IlyaGazman Actually, reading your question a second time, I see that you have the requirement that $a \leq b$, so the answer is just $\varphi(n)$. If the question instead just said $0 < a,b < n$, then you'd need to be a bit more careful counting the number of pairs -- the naive answer would be $2\varphi(n)$ (as then if $(a,b)$ is such a pair, $(b,a)$ would also be a pair), except this could double-count any pair $(a,a)$ for which $a^2 \equiv 1 \mod n$ (such as $2^2 \equiv 1 \mod 3$). But the requirement that $a\leq b$ dispenses with this issue. – Hayden Jul 15 '20 at 00:55

0 Answers0