Primes are very cruel

Number Theory Level 2

p q − 1 + q p − 1 ≡ r ( m o d p q ) \large\displaystyle p^{q-1} + q^{p-1}\equiv r \pmod {pq}

Let p p and q q be distinct prime numbers , find the smallest positive value of r r satisfying the congruence above.


The answer is 1.

View wiki
Kushal Bose by Kushal Bose , 28, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Using euler's totient function , q p − 1 ≡ 1 ( m o d p ) q^{p-1} \equiv 1 \pmod{p} and p q − 1 ≡ 1 ( m o d q ) p^{q-1} \equiv 1 \pmod{q} .

Hence, we have
p q − 1 + q p − 1 ≡ 0 + 1 ≡ 1 ( m o d p ) p^{q-1} + q^{p-1} \equiv 0 + 1 \equiv 1 \pmod{p} ,
p q − 1 + q p − 1 ≡ 1 + 0 ≡ 1 ( m o d q ) p^{q-1} + q^{p-1} \equiv 1 + 0 \equiv 1 \pmod{q} .

Thus, by the chinese remainder theorem , p q − 1 + q p − 1 ≡ 1 ( m o d p q ) p^{q-1} + q^{p-1} \equiv 1 \pmod{pq} .

4 Helpful 0 Interesting 0 Brilliant 0 Confused

@Mayank Chaturvedi I like your solution and have converted it into a solution. In future, please add solutions directly instead of leaving them in comments. Thanks!

Calvin Lin Staff - 4 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...