# Is a number congruent to 1 mod 4 divisible by a number congruent to 3 mod 4

I am almost certain of the answer to this question, but cannot seem to find something to confirm it, and I feel the proof is too simple to be correct. I have studied modular arithmetic a decent bit, but am too uncomfortable in the subject to feel confident in my answer. If this is a duplicate I apologize and request to be directed to the correct answer.

The question: If a number is congruent to 1 mod 4, can it ever be divisible by a number congruent to 3 mod 4. More specifically, for positive integers $a$ and $b$, we know $a \equiv 1 (\textrm{mod} 4)$ and $b \equiv 3 (\textrm{mod} 4)$. Can $b | a$?

• 3|9    – Exodd Apr 8 '17 at 17:12
• Right--take any number that's 3 mod 4 and square it. – Elizabeth S. Q. Goodman Apr 8 '17 at 17:14

## 3 Answers

Counterexample, for odd $n$: $$a=3^{2n}, b = 3^{n}$$

• Thanks, that was extremely simple. Must just be a bit brain-dead right now. Thanks for the help. – Nathan Apr 8 '17 at 17:16

The product of two numbers congruent to $3$ mod $4$ is always congruent to $1$ mod $4$. For example, $3\cdot 7=21$.

Here is my favourite example: Take $a=57$, the Grothendieck's Prime!!