# Modular math

• May 21st 2010, 04:25 PM
1337h4x
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) ?
• May 21st 2010, 04:31 PM
tonio
Quote:

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
• May 21st 2010, 04:34 PM
1337h4x
Quote:

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$
• May 21st 2010, 06:51 PM
tonio
Quote:

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$ (Wondering)

Tonio
• May 21st 2010, 08:47 PM
hollywood
Quote:

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
• May 21st 2010, 09:05 PM
undefined
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.