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

• MHB
• Petek
In summary, divisibility is the property of a number being able to be evenly divided by another number without leaving a remainder. To prove divisibility, we can use the division algorithm and the formula for linear combinations. Proving divisibility of 5c+9d and 3c+10d by 23 is important because it helps us determine if a number is a multiple of 23, which has various practical applications.
Petek
Gold Member
Let c and d be integers. Suppose that 5c + 9d is divisible by 23. Show that 3c + 10d also is divisible by 23.

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

@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.

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$.

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$.

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

## 1. How do you prove the divisibility of 5c+9d and 3c+10d by 23?

To prove the divisibility of 5c+9d and 3c+10d by 23, we can use the divisibility rule for 23. This rule states that if the alternating sum of the digits in a number is divisible by 23, then the number itself is also divisible by 23.

## 2. What is the alternating sum of digits in a number?

The alternating sum of digits in a number refers to the process of taking the sum of the digits in a number, but alternating the signs between positive and negative. For example, the alternating sum of digits in the number 123 would be 1 - 2 + 3 = 2.

## 3. Can you provide an example of using the divisibility rule for 23?

Sure, let's take the numbers 42 and 69. To prove their divisibility by 23, we first calculate the alternating sum of digits for each number. For 42, the alternating sum would be 4 - 2 = 2. For 69, the alternating sum would be 6 - 9 = -3. Since both of these sums are divisible by 23 (2/23 = 0.087 and -3/23 = -0.130), we can conclude that both 42 and 69 are divisible by 23.

## 4. Is the divisibility rule for 23 always accurate?

Yes, the divisibility rule for 23 is always accurate. This rule is based on the fact that 10^2 ≡ -1 (mod 23). This means that any number can be written as a sum of its digits multiplied by powers of 10, and this sum will be congruent to the alternating sum of digits (with alternating signs) modulo 23. Therefore, if the alternating sum is divisible by 23, the number itself is also divisible by 23.

## 5. Are there any other methods for proving divisibility of 5c+9d and 3c+10d by 23?

Yes, there are other methods for proving divisibility of 5c+9d and 3c+10d by 23. One method is to use modular arithmetic and congruence relations. Another method is to express the numbers in terms of their prime factorizations and use the properties of prime numbers to show that they are divisible by 23. However, the divisibility rule for 23 is often the most efficient and straightforward method for proving divisibility in this case.

Replies
1
Views
1K
Replies
1
Views
797
Replies
1
Views
1K
Replies
7
Views
3K
Replies
22
Views
3K
Replies
5
Views
2K
Replies
2
Views
1K
Replies
4
Views
1K
Replies
9
Views
2K
Replies
1
Views
1K