Modular math

Apr 2009
96
0
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) ?
 
Oct 2009
4,261
1,836
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
 
Apr 2009
96
0
\(\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\)
 
Oct 2009
4,261
1,836
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
 
Mar 2010
1,055
290
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
 
  • Like
Reactions: 1337h4x

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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.