# Modular math

#### 1337h4x

This is a quick question on Modular Math:

How can I prove that n = 1 (mod 4) IFF n = 1 (mod 8) or n = 5 (mod 8) ?

#### tonio

This is a quick question on Modular Math:

How can I prove that n = 1 (mod 4) IFF n = 1 (mod 8) or n = 5 (mod 8) ?

$$\displaystyle n=1\!\!\!\pmod 4\Longrightarrow n$$ is odd, so it must be $$\displaystyle n=1,3,5\,\,or\,\,7\!\!\!\pmod 8$$, but $$\displaystyle n=3\!\!\!\pmod 8\Longrightarrow n=3\!\!\!\pmod 4$$...with 7 is similar.

Tonio

#### 1337h4x

$$\displaystyle n=1\!\!\!\pmod 4\Longrightarrow n$$ is odd, so it must be $$\displaystyle n=1,3,5\,\,or\,\,7\!\!\!\pmod 8$$, but $$\displaystyle n=3\!\!\!\pmod 8\Longrightarrow n=3\!\!\!\pmod 4$$...with 7 is similar.

Tonio

Can you explain this part:

$$\displaystyle n=1,3,5\,\,or\,\,7\!\!\!\pmod 8$$, but $$\displaystyle n=3\!\!\!\pmod 8\Longrightarrow n=3\!\!\!\pmod 4$$

#### tonio

Can you explain this part:

$$\displaystyle n=1,3,5\,\,or\,\,7\!\!\!\pmod 8$$, but $$\displaystyle n=3\!\!\!\pmod 8\Longrightarrow n=3\!\!\!\pmod 4$$

$$\displaystyle n=3\!\!\!\pmod 8\Longrightarrow n=3+8k=3+(2k)4\Longrightarrow n=3\!\!\!\pmod 4$$ (Wondering)

Tonio

#### hollywood

This is a quick question on Modular Math:

How can I prove that n = 1 (mod 4) IFF n = 1 (mod 8) or n = 5 (mod 8) ?
By the definition of congruence, $$\displaystyle n\equiv{1}\ (\text{mod }4)$$ means 4 divides n-1. Since $$\displaystyle \frac{n-1}{4}$$ is an integer, it must be odd or even. So $$\displaystyle \frac{n-1}{4}=2m\text{ or }2m+1$$, where m is an integer. Solving both for m gives $$\displaystyle m=\frac{n-1}{8}\text{ or }\frac{n-5}{8}$$ so $$\displaystyle n\equiv{1}\text{ or }5\ (\text{mod }8)$$. And, of course, you can reverse the argument.

- Hollywood

1337h4x

#### undefined

MHF Hall of Honor
It's the same reason that an odd number is either congruent to 1 or 3 (mod 4). Of course numbers congruent to 0 or 2 (mod 4) are even.