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

1.2k Views Asked by At

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

There are 3 best solutions below

1
On

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

0
On

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

0
On

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