Albert has a very large bag of candies and he wants to share all of it with his friends. At first, he splits the candies evenly amongst his $20$ friends and himself and he finds that there are five left over. Ante arrives, and they redistribute the candies evenly again. This time, there are three left over. If the bag contains over $500$ candies, what is the fewest number of candies the bag can contain?
1. Let \( x \) be the total number of candies. According to the problem, when Albert splits the candies among his 20 friends and himself (21 people in total), there are 5 candies left over. This can be expressed as:
   \[
   x \equiv 5 \pmod{21}
   \]
   
2. When Ante arrives, making the total number of people 22, and they redistribute the candies, there are 3 candies left over. This can be expressed as:
   \[
   x \equiv 3 \pmod{22}
   \]

3. We need to solve the system of congruences:
   \[
   \begin{cases}
   x \equiv 5 \pmod{21} \\
   x \equiv 3 \pmod{22}
   \end{cases}
   \]

4. To solve this system, we use the method of successive substitutions or the Chinese Remainder Theorem. First, we express \( x \) in terms of the first congruence:
   \[
   x = 21k + 5 \quad \text{for some integer } k
   \]

5. Substitute \( x = 21k + 5 \) into the second congruence:
   \[
   21k + 5 \equiv 3 \pmod{22}
   \]

6. Simplify the congruence:
   \[
   21k + 5 \equiv 3 \pmod{22} \implies 21k \equiv -2 \pmod{22}
   \]

7. Since \(-2 \equiv 20 \pmod{22}\), we have:
   \[
   21k \equiv 20 \pmod{22}
   \]

8. Notice that \( 21 \equiv -1 \pmod{22} \), so:
   \[
   -k \equiv 20 \pmod{22} \implies k \equiv -20 \pmod{22} \implies k \equiv 2 \pmod{22}
   \]

9. Therefore, \( k = 22m + 2 \) for some integer \( m \). Substitute back into \( x = 21k + 5 \):
   \[
   x = 21(22m + 2) + 5 = 462m + 47
   \]

10. Thus, we have:
   \[
   x \equiv 47 \pmod{462}
   \]

11. Since \( x > 500 \), we find the smallest \( x \) by setting \( m = 1 \):
   \[
   x = 462 \cdot 1 + 47 = 509
   \]

The final answer is \(\boxed{509}\).