Inspired by Dylan Pentland

Number Theory Level 5

$36^a\equiv 84^b\pmod{101}$

How many ordered pairs $(a,b)$ of integer solutions does the above congruency have, where $1\leq a \leq 100$ and $1\leq b \leq 100$ ?

The answer is 2000.

1 solution

Andy Hayes
Oct 29, 2015

We can calculate the following:

$36^1\equiv36\pmod{101}$

$36^2\equiv84\pmod{101}$

$36^3\equiv95\pmod{101}$

$36^4\equiv87\pmod{101}$

$36^5\equiv1\pmod{101}$

Since the final power in this sequence is equivalent to $1$ , the pattern continues for subsequent powers.

Likewise:

$84^1\equiv84\pmod{101}$

$84^2\equiv87\pmod{101}$

$84^3\equiv36\pmod{101}$

$84^4\equiv95\pmod{101}$

$84^5\equiv1\pmod{101}$

For each value of $a$ , there are $20$ corresponding values of $b$ . With $100$ possible values of $a$ , there are a total of $\boxed{2000}$ possible ordered pairs.

Yes, exactly! Thank you for a clear and detailed solution (+1)! The key fact to observe is that both 36 and 84 have order 5 in $(\mathbb{Z}/101\mathbb{Z})^*$

Otto Bretscher - 5 years, 7 months ago

Is there a way to determine they both an order 5 without listing out the first few powers?

Pi Han Goh - 5 years, 7 months ago

I'm not aware of a shortcut... are you? It suffices to check the powers of one of them, of course. Alternatively, you could check the powers $36^2,36^5,36^{10}$ and $36^{25}$ since the order has to divide 100 (and, in fact, 50 since 36 is a square).

Otto Bretscher - 5 years, 7 months ago

@Otto Bretscher – Nope. I thought you knew some tricks up your sleeve.

Pi Han Goh - 5 years, 7 months ago

Inspired by Dylan Pentland

The answer is 2000.

1 solution

0 pending reports