1. ## Modular math

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) ?

2. Originally Posted by 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) ?

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

Tonio

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

Tonio

Can you explain this part:

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

4. Originally Posted by 1337h4x
Can you explain this part:

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

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

Tonio

5. Originally Posted by 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) ?
By the definition of congruence, $n\equiv{1}\ (\text{mod }4)$ means 4 divides n-1. Since $\frac{n-1}{4}$ is an integer, it must be odd or even. So $\frac{n-1}{4}=2m\text{ or }2m+1$, where m is an integer. Solving both for m gives $m=\frac{n-1}{8}\text{ or }\frac{n-5}{8}$ so $n\equiv{1}\text{ or }5\ (\text{mod }8)$. And, of course, you can reverse the argument.

- Hollywood

6. 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.