Basic Techniques for Solving Theory of Congruence Problems - 1

8 Basic Techniques for solving theory of congruence/Modular Arithmetic problems summarised from my solution on Chapter 4.2 Elementary Number Theory 7th Edition Problems (David M. Burton).

Ran
Ran

Background

These are some techniques that I summarized based on my solution on Chapter 4.2 of Elementary Number Theory 7th Edition Problems (the book is written by David M. Burton).

Elementary Number Theory (Paperback)
Get it now:

8 Basic Techniques

Always Try to Make It Congruent to $1$ Or $-1$

For example, from Chapter 4.2 Q4, can you calculate the remainder when $41^{65}$ is divisible by $7$ instantly? Or calculate the value for $41^{65} \pmod 7$?

How?

$41^{65} \equiv (-1)^{65} \equiv -1 \equiv 6 \pmod 7$

Why?

Well, you can think of it in two ways: either $41 - (-1) = 6(7)$ or $41 - 42 = 41 - 6(7) = -1$. Then we add $7$ to $-1$ to see what is the remainder that we are finding.

Consider the Smaller Power Like $2$ Or $3$ First

For example, from Chapter 4.2 Q4, can you calculate $2^{50} \pmod 7$ instantly?

How?

Consider $2^{2}$ or $2^{3} \pmod 7$. Can it be $1 \pmod 7$? It works for $2^{3}$. So we can break down the larger power like $2^{50}$ into $(2^{3}) ^{16} \cdot 2^{2}$.

Expand Everything Except the Variable in Power First

The rest is for Premium Members only (7 days free trial)

Subscribe

Already have an account? Log in