MHB Proving Divisibility of 5c+9d and 3c+10d by 23

[Petek]

Let c and d be integers. Suppose that 5c + 9d is divisible by 23. Show that 3c + 10d also is divisible by 23.

 

[kaliprasad]

Spoiler: My Solution

5c + 9d is divisible by 23
multiplying by 15
75c + 135d is divisible by 23

subtracting 69c + 115d a multiple of 23 we have

6c + 20d is divisible by by 23

or 2(3c+ 10d) is divisible by by 23

as 2 is not divisible by 23 so 3c + 10d is divisible by 23

 

[Petek]

@kaliprasad Thanks for your solution. In addition to yours, I found a second solution that requires more knowledge about elementary number theory. As a hint, it uses facts about Diophantine equations. I'll post again in a few days if no one finds what I was thinking of.

 

[I like Serena]

Spoiler: My attempt

First observe that $5^{-1}\equiv -9\pmod{23}$. That is because $5\cdot -9\equiv -45 \equiv 1\pmod{23}$.

That fact that $5c+9d$ is divisible by $23$ means:
\[ 5c + 9d\equiv 0\pmod{23}\implies c\equiv 5^{-1}\cdot -9d\pmod{23}\implies c\equiv -9\cdot -9 d\equiv 81 d\equiv 12d\pmod{23} \]
Therefore:
\[ 3c + 10d \equiv 3\cdot 12d+10d\equiv 46 d\equiv 0 \pmod{23} \]
So $3c + 10d$ is also divisible by $23$.

 

[I like Serena]

Spoiler: Alternate attempt

The solutions of $23\mid 5c+9d$ are $c=-9+23k$ and $d=5+23m$.
Substitute in $3c+10d$ to find $3(-9+23k)+10(5+23m)=-23+23(3k+10m)$, which is divisible by $23$.

 

[Petek]

Klass' second solution is the alternate one that I had in mind. Thanks to all for their contributions.