Find $4^{-1} \pmod{35}$, as a residue modulo 35.  (Give an answer between 0 and 34, inclusive.)
Since $4 \cdot 9 = 36 \equiv 1 \pmod{35}$, $4^{-1} \equiv \boxed{9} \pmod{35}$.
9
Level 4
Number Theory
Problem: Find $4^{-1} \pmod{35}$, as a residue modulo 35.  (Give an answer between 0 and 34, inclusive.)
Solution:<|START_OF_LATENT|><|PRIOR_PREFIX|>To find the modular inverse of 4 modulo 35, we need to determine an integer \( x \) such that \( 4x \equiv 1 \pmod{35} \). This means that when \( 4x \) is divided by 35, the remainder should be 1.

First, we check if 4 has an inverse modulo 35 by confirming that the greatest common divisor (gcd) of 4 and 35 is 1. Since 4 is even and 35 is odd, their gcd is indeed 1, indicating that an inverse exists.

Next, we can use the Extended Euclidean Algorithm to find the inverse. We start with the equation:

1. \( 35 = 8 \times 4 + 3 \)
2. \( 4 = 1 \times 3 + 1 \)
3. \( 3 = 3 \times 1 + 0 \)

Now, we backtrack to express 1 as a linear combination of 4 and 35:

From step 2, we have:

1. \( 1 = 4 - 1 \times 3 \)

Substituting for 3 from step 1:

1. \( 3 = 35 - 8 \times 4 \)

Substituting this into the equation for 1 gives:

1. \( 1 = 4 - 1 \times (35 - 8 \times 4) \)
2. \( 1 = 4 - 35 + 8 \times 4 \)
3. \( 1 = 9 \times 4 - 35 \)

This shows that \( 9 \times 4 \equiv 1 \pmod{35} \). Therefore, \( x = 9 \) is the modular inverse of 4 modulo 35.

Finally, since we need the answer to be between 0 and 34, we confirm that 9 is within this range. Thus, the final answer is 9.<|END_OF_LATENT|> The final answer is $9$.