• 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!