Primes, divisors, and congruences