1

So as an exercise I'm trying to figure out which largest negative fulfills 8x+7≡3 (mod 35)

I have solved the x, x=17, but honestly I have no idea where to go from here.

Maybe 17-35=(-18)?

I'd appreciate any pointers and help.

Thanks for your time.

Talar
  • 35
  • 5
  • 2
    Yes, $-18$ (there is no solution inbetween because 35 and 8 are coprime: if $8x+7\equiv3\equiv8\cdot17+7\bmod{35}$, i.e. if $35\mid8(x-17)$, then $35\mid x-17$). – Anne Bauval Oct 03 '22 at 18:58
  • 4
    As you say, we have $x \equiv 17 ,(\text{mod } 35)$. So $17$ is a solution, but also any number which is of the form $35k + 17$ for some $k \in \mathbb{Z}$ will work. Setting $k= -1$ gives you the largest negative number, namely $-18$, as you said. – Dylan Oct 03 '22 at 18:58

1 Answers1

2

If $$8x + 7 \equiv 3 \pmod {35}$$ this means that $8x + 7$ leaves a remainder of $3$ when divided by $35$; i.e., $$8x + 7 = 35q + 3$$ for some integer $q$ (which is called the quotient). This gives us $$35q = 8x + 4 = 4(2x+1).$$ Since $4$ does not divide $35$, it must divide $q$. So suppose $q = 4m$; we get

$$35m = 2x+1.$$

What is the largest $x < 0$ that satisfies this equation for integers $m$? well, the largest $m$ such that $35m$ is a negative integer is $m = -1$; hence $2x + 1 = -35$ or $$x = -18.$$

We can also characterize the full set of $x$ that satisfies the original congruence: we have $$x \in \{\ldots, -88, -53, -18, 17, 52, 87, \ldots \}.$$ That is, $x = 35m + 17$ for any integer $m$.

heropup
  • 135,869