Find the number of integer pairs 0 ≤ a, b ≤ 100 such that $a^{20}$ ≡ $b^{50} \pmod {101}$.
Here is the solution: "Since is prime, there exists a primitive
root g in modulo 101. For some integers x and y, with 1 ≤ x, y ≤ 100, let a ≡ $g^x$ and b ≡ $g^y$. Hence, $g^{20x}$ ≡ $g^{50y}$ (mod 101). Therefore, $g^{20x−50y}$ ≡ 1 (mod 101), and 100|20x − 50y, or alternatively, 10|2x − 5y. Since 2|2x − 5y, we have 2|y. Also, 5|2x − 5y, so 5|x. Hence, the congruence holds for all x and y such that x is a multiple of 5 and y is a multiple of 2. There are 20 choices for x and 50 choices for y, so our answer is 20 · 50 = 1000."
In general, I'm very confused on the logical reasoning behind these steps. I'm a beginner in learning primitve roots and perhaps don't have enough background yet.
I'm confused why you can let a ≡ $g^x$ and b ≡ $g^y$. Wouldn't that mean both $g^{x}$ and $g^{y}$ are both one Modulo 101? Finally, why does 100 have to divide 20x-50y. In fact, shouldn't it be 20x-50y dividing 100? I thought ord(a) of x always has to divide totient of x, and therefore 20x-50y|totient 101 which is 100.
Best Answer
The set ${\mathbb Z}_{101}$ of integer remainders modulo $101$ is an additive group. It is obvious that $({\mathbb Z}_{101},+)$ is cyclic, and is generated, e.g., by $1$.
Since $101$ is a prime number, the set ${\mathbb Z}^*_{101}$ of nonzero elements in ${\mathbb Z}_{101}$ is a multiplicative group with $100$ elements.
It is a theorem of elementary number theory that this multiplicative group $({\mathbb Z}^*_{101},\cdot)$ is cyclic as well. This means that we can find elements $g\in{\mathbb Z}^*_{101}$ such that $$\bigl\{g^k\>\bigm|\>1\leq k\leq 100\bigr\}={\mathbb Z}^*_{101}\ .$$ There is no simple general way for finding such generators $g$. Trying with $2$ showed that all numbers $2^n$ $(1\leq n\leq100)$ have different remainders modulo $101$. Therefore we could think of $g=2$ in our problem. In particular $g^{100}=1$.
When $a$ and $b$ are any numbers in $[1\,..\,100]$ (this is a set of representatives for ${\mathbb Z}^*_{101}$) then there are uniquely determined integers $x$, $y\in[1\,..\,100]$ such that $g^x=a$ modulo $101$ and $g^y=b$ modulo $101$. Since we want $a^{20}=b^{50}$ we need $$g^{20x}= g^{50y},\quad{\rm resp.,}\quad g^{20x-50y}=1\qquad({\rm mod}\ 101)\ ,$$ and this is the case iff $20x-50y$ is a multiple of $100$, or $$x, \>y\in[1\,..\,100],\qquad2x-5y=0\quad({\rm mod}\ 10)\ .$$ The latter congruence necessitates that $x$ is divisible by $5$ and $y$ is divisible by $2$.