We find a formula for the probability that the product of n positive integers, chosen at random, is divisible by some integer d. We do this via an inductive application of the Chinese Remainder Theorem, generating functions, and several other combinatorial arguments. Additionally, we apply this formula to find a unique, but slow, probabilistic primality test.

Author Bio

Noah Fine completed the submitted work prior to his graduation from the University of Maryland, College Park, in the spring of 2023. Noah studied mathematics and computer science, and currently utilizes his knowledge of these subjects in his role at The MITRE Corporation. In his free time, Noah enjoys solving probability puzzles, studying various Jewish texts, and playing competitive Mario Kart.