Some notes about this
-
I think that when you have a problem that says something like "How many numbers, from 1 to a, when multiplied by b, have a remainder of c (mod d)", the answer will always be a/d.
I think this is true because there will always be a number e (mod d) that when multiplied by b, has a remainder of c (mod d). The number e will occur once every d numbers, so it will occur a/d times in the numbers 1 to a.
Now if a is not a multiple of d, it might happen a/d times rounded down or up. This depends on the remainder when a is divided by d... if the remainder is less than e then it is a/d rounded down, if the remainder is more than e it is a/d rounded up.
-
Hey @tidyboar, great observations you're making! I agree with a lot of what you're saying. The thing is, all of that works when \(d\) is prime. For example, how many numbers from \(1\) to \(5\), when multiplied by \(3\), is \( \equiv 1 \text{ (mod 6)}\)?
When you make the table, you'll realize that all of the numbers after being multiplied are either \( 0 \text{ (mod 6)}\) or \( 3 \text{ (mod 6)}\), so actually none of the numbers are \( 1 \text{ (mod 6)}\) The reason why this doesn't work is because \(3\) is a factor of \(6\)! And actually, you can remake this problem with any even number and you'll find that there are a lot of exceptions.
BUT, what you said is actually really useful!! Number theory often involves prime numbers, so everything you figured out will save you a lot of time when actually doing problems. Way to go for understanding everything!
