+174 Let x and y be integers. Show that 9x+5y is divisible by 19 if and only if x+9y is divisible by 19.
We can start by plugging in values.
If we let x = 1 and y = 2, then 9x + 5y = 19 and x + 9y = 19. We can add multiple of 9 to another number which is the remainder when the number is divided by 9 to get a multiple of 19.
We can also try other values, like x = 2 and y = 1. Then 9x + 5y = 23 and x + 9y = 11, so these numbers are not divisible by 19. We add a multiple of 9 to another number which is not the remainder when the number is divided by 9, which is why the numbers are not divisible by 19.
We can create congruences to account for the conditions in the problem. We want both 9x + 5y and x + 9y to be divisible by 19, so 9x + 5y == 0 (mod 19) and x + 9y == 0 (mod 19). Therefore, 9x + 5y == x + 9y (mod 19). This simplifies to 8x == 4y (mod 19). Then y == 2x (mod 19).
This tells us that the only cases where both 9x + 5y and x + 9y are divisible by 19 are the cases where y = 2x, like the case x = 1 and y = 2 we looked at above. Every other solution will be a multiplicative scale of this solution (like x = 2 and y = 4, or x = 3 and y = 6). This proves the result.
