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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 16, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}