# Congruence of certain numbers mod a large prime

I have a set of small prime numbers $S = \{2,3,5,7,11,13,17,19,23,29\}$.

By multiplying those I can form other numbers, by assigning to each element of the set an exponent of $0$ or $1$, so that I can form $2^{10}$ different numbers in total--because there are ten elements in the set. So let's say I call the set of all such numbers $T$.

I also have a (large) prime, around $10^6$, which I call $p$.

Let's call the set of numbers in $T$, reduced $\bmod p$, $T_p$. Are all elements of $T_p$ different, as is the case for $T$? If yes, how would one prove that? If not, please give an example.

This is not an exercise, so I have no reference. The answer might be positive or negative, but I need some input to find out. :) (Also, if anyone can word the title a bit better that I have, please do provide suggestions)

• So you are asking if there are distinct subsets of S whose products are congruent mod p? – Bill Dubuque Apr 7 '15 at 1:56
• Yes that's it. I figured I'd make another set to make it clearer, but that's the same thing. – Snowflake Apr 7 '15 at 2:10
• Do you have a specific $p$ in mind? It may well depend on which $p$ you choose. – Qudit Apr 7 '15 at 2:21
• The product of all of these is $6,469,693,230$. Many of the products will be smaller than your $p$ and we know they are distinct. As you delete factors you will fall down towards $10^6$ quickly, so it seems clear that for most primes around $10^6$ there will not be a match mod $p$. – Ross Millikan Apr 7 '15 at 2:42
• Yes @RossMillikan, I was wondering though if it was the case that no match exists. – Snowflake Apr 7 '15 at 3:36

From SAGE: sage: factor$(2*3*5*7*11*17*19*23*29 -13)$
$67 * 7427891$