Base Conversion and Modular Arithmetic

You know how we count in base 10? That’s just a convention. We could count in any base. Computers use base 2 (binary). Programmers use base 16 (hexadecimal). Mathematicians use whatever base makes the problem easier.

And then there’s modular arithmetic—basically clock math. It shows up everywhere in competitions and makes huge problems manageable.

Let’s talk about both.

Base Conversion: Same Number, Different Representation

The Idea

In base 10, each digit represents a power of 10. The number 123 means $1 \times 10^2 + 2 \times 10^1 + 3 \times 10^0$.

In base 2 (binary), each digit represents a power of 2. The number $101101_2$ means $1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 45$.

Same number, different way of writing it.

Converting to Binary (The Easy Way)

Want to convert 45 to binary? Keep dividing by 2 and write down the remainders:

• $45 \div 2 = 22$ remainder $1$
• $22 \div 2 = 11$ remainder $0$
• $11 \div 2 = 5$ remainder $1$
• $5 \div 2 = 2$ remainder $1$
• $2 \div 2 = 1$ remainder $0$
• $1 \div 2 = 0$ remainder $1$

Now read the remainders from bottom to top: $101101_2$. That’s it.

Check: $1 \times 32 + 0 \times 16 + 1 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1 = 45$. ✓

Other Bases

Same trick works for any base. Converting 314 to base 5?

• $314 \div 5 = 62$ remainder $4$
• $62 \div 5 = 12$ remainder $2$
• $12 \div 5 = 2$ remainder $2$
• $2 \div 5 = 0$ remainder $2$

So $314_{10} = 2224_5$.

Hexadecimal (Base 16)

This one’s fun because we need 16 digits. We use 0-9, then A-F for 10-15.

Converting 255 to hex:

• $255 \div 16 = 15$ remainder $15$ (that’s F)
• $15 \div 16 = 0$ remainder $15$ (that’s F again)

So $255_{10} = FF_{16}$. Neat, right?

Converting Back to Base 10

This is easier. Just multiply each digit by its place value and add.

$101101_2 = 1 \times 32 + 0 \times 16 + 1 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1 = 45$.

$3A7_{16}$? A is 10, so: $3 \times 256 + 10 \times 16 + 7 \times 1 = 768 + 160 + 7 = 935$.

The Shortcut for Powers of 2

Converting between binary and octal (base 8) or hex (base 16) is super easy because 8 and 16 are powers of 2.

For binary to octal: group digits in threes from right to left. $101101_2$ becomes $101$ $101$, which is $5_8$ $5_8$, so $55_8$.

For binary to hex: group digits in fours. $101101_2$ becomes $0010$ $1101$ (pad with zeros), which is $2_{16}$ $D_{16}$, so $2D_{16}$.

Modular Arithmetic: Clock Math

The Basic Idea

Modular arithmetic is about remainders. When you work “modulo $n$,” you only care about what’s left after dividing by $n$.

$17 \equiv 2 \pmod{5}$ because both 17 and 2 leave remainder 2 when divided by 5. Or equivalently, because $17 - 2 = 15$ is divisible by 5.

It’s like a clock. On a 12-hour clock, 13 o’clock is 1 o’clock. That’s $13 \equiv 1 \pmod{12}$.

Why It’s Useful

It makes huge problems small. Want the last digit of $7^{2025}$? Work modulo 10.

Find the pattern:

• $7^1 \equiv 7 \pmod{10}$
• $7^2 = 49 \equiv 9 \pmod{10}$
• $7^3 = 343 \equiv 3 \pmod{10}$
• $7^4 = 2401 \equiv 1 \pmod{10}$
• $7^5 = 7^4 \cdot 7 \equiv 1 \cdot 7 \equiv 7 \pmod{10}$

It repeats every 4. Since $2025 = 4 \times 506 + 1$, we have: $7^{2025} = 7^{4 \times 506 + 1} = (7^4)^{506} \cdot 7^1 \equiv 1^{506} \cdot 7 \equiv 7 \pmod{10}$

So the last digit is 7. No need to compute $7^{2025}$.

The Rules

Modular arithmetic plays nice with addition, subtraction, and multiplication:

• If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $a+c \equiv b+d \pmod{n}$
• Same for subtraction and multiplication

Division is trickier. You can’t just divide both sides unless you’re careful.

Fermat’s Little Theorem

Here’s a powerful shortcut: if $p$ is prime and $a$ isn’t divisible by $p$, then $a^{p-1} \equiv 1 \pmod{p}$.

Want $5^{100} \bmod 7$? Since 7 is prime and 5 isn’t divisible by 7, we know $5^6 \equiv 1 \pmod{7}$.

Since $100 = 6 \times 16 + 4$: $5^{100} = (5^6)^{16} \cdot 5^4 \equiv 1^{16} \cdot 5^4 \equiv 625 \equiv 2 \pmod{7}$

Done. No giant calculations.

Finding Patterns

Many competition problems involve finding patterns in powers. The key is to compute a few small powers, see the pattern, then use it.

For $2^{100} \bmod 7$:

• $2^1 \equiv 2$
• $2^2 \equiv 4$
• $2^3 = 8 \equiv 1$

Pattern repeats every 3. Since $100 = 3 \times 33 + 1$, the answer is $2^1 \equiv 2$.

Where You’ll See This

Base conversion shows up in:

• Computer science (binary, hex)
• Competition problems
• Cryptography
• Understanding how computers work

Modular arithmetic shows up in:

• Competition problems (constantly)
• Cryptography (RSA encryption)
• Calendar calculations
• Finding last digits, remainders, patterns

The Takeaway

Both topics seem abstract, but they’re incredibly practical. Base conversion helps you understand how numbers work at a fundamental level. Modular arithmetic makes impossible problems possible.

The key is recognizing when to use them. If a problem asks about remainders, last digits, or divisibility, think modular arithmetic. If it asks about number representations or computer-related math, think base conversion.

Practice both. They’ll save you time and make you look like a genius.