1

As the question titles states, how can I efficiently find whether $d + \frac{n}{d} \equiv 0 \pmod 4$, given that $d$ divides $n$? An example would be with $n = 35$ and $d = 5$.

$5 + \frac{35}{5} = 5+7 = 12 \equiv 0 \pmod 4$, so it "passes". I tried $d + \frac{n}{d} \equiv 0 \pmod 4$, so $\frac{n}{d} \equiv -d \pmod 4$. This means that $n$ must equal $-d^{2}$ (mod 4). Can someone let me know if this is right? If not, what is a good way/are some preconditions of $d$ and $n$ so that $d + \frac{n}{d} \equiv 0 \pmod 4$.

Varun Vejalla
  • 8,873
  • $-d \not\equiv d \pmod{4}$ in general (e.g., $d=3$). In fact, this is only true if $d \equiv 0 \pmod{4}$ or $d \equiv 2 \pmod{4}$. Also, it's not enough to have conditions on $d$, you will also need conditions on $n$. – kccu May 02 '19 at 00:51
  • I think I fixed it. Let me know if there's anything else that needs revision. – Varun Vejalla May 02 '19 at 00:54
  • I am not sure if this is right, but $-d^2 \mod{4} = -d^2 \mod{2} = d^2 \mod{2}$? – Gareth Ma May 02 '19 at 00:55
  • @GarethMa That is true, but that loses you information. You go from $n \equiv -d^2 \pmod{4}$ (which means either $n \equiv 0 \pmod{4}$ or $n \equiv -1 \pmod{4}$) to $n \equiv d^2 \pmod{2}$ (which could, a priori, give you any remainder modulo $4$). – kccu May 02 '19 at 00:59
  • @automaticallyGenerated Your equation $n \equiv -d^2 \pmod{4}$ is fine, why do you say it is "definitely not right"? – kccu May 02 '19 at 01:00
  • @automaticallyGenerated In fact that gives you exactly your answer. You have $(d + n/d) \equiv 0 \pmod{4}$ if and only if $d$ divides $n$ and $n \equiv -d^2 \pmod{4}$. Those are the conditions on $n$ and $d$. – kccu May 02 '19 at 01:05
  • What @GarethMa said seemed right to me, so I changed the question. If you can't tell already, I am extremely confused about modular arithmetic. I changed the question back. – Varun Vejalla May 02 '19 at 01:06
  • Also, I agree with the "only if" part of your statement, but it's not the only condition. For example, if $n = 12$ and $d = 4$, $12 \equiv -16 \pmod 4$, but $4+12/4 \equiv 3 \pmod 4$ – Varun Vejalla May 02 '19 at 01:18

1 Answers1

1

If $n$ is odd, then $d$ is odd. In that case $d+(n/d)\equiv 0$ iff $x^2\equiv -n$ because $d$ is a unit $\bmod 4$. But for odd $d$ we must have $d^2\equiv 1$, so the ordered pair $(n,d)$ passes for odd $n$ iff $n\equiv 3\bmod 4$.

If $n$ is even, then $d$ and $n/d$ must both be even (meaning $n$ is a multiple of $4$). Assuming this parity requirement is met, then either both $d$ and $n/d$ must be twice an odd number so $d+(n/d)\equiv 2+2$, like $n=12, d=2$, or else both $d$ and $n/d$ must be multiples of $4$. Among even values of $n$, all multiples of $16$ will have at least one $d$ meeting this criterion, and all remaining multiples of $4$ that are not multiples of $8$ will also have at least one such $d$.

All told, $7/16$ of all $n$ values ($n\in \{0,3,4,7,11,12,15\}\bmod 16$) will have at least one passing value of $d$.

Oscar Lanzi
  • 39,403