1
$\begingroup$

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)

Improve this question
$\endgroup$
  • 1
    $\begingroup$ So you are asking if there are distinct subsets of S whose products are congruent mod p? $\endgroup$ – Bill Dubuque Apr 7 '15 at 1:56
  • 1
    $\begingroup$ Yes that's it. I figured I'd make another set to make it clearer, but that's the same thing. $\endgroup$ – Snowflake Apr 7 '15 at 2:10
  • $\begingroup$ Do you have a specific $p$ in mind? It may well depend on which $p$ you choose. $\endgroup$ – Qudit Apr 7 '15 at 2:21
  • $\begingroup$ 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$. $\endgroup$ – Ross Millikan Apr 7 '15 at 2:42
  • $\begingroup$ Yes @RossMillikan, I was wondering though if it was the case that no match exists. $\endgroup$ – Snowflake Apr 7 '15 at 3:36
1
$\begingroup$

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

$67 * 7427891$

So the prime number above exceeding 7 million divides the difference between 13 and the product of the nine prime numbers < 30 after excluding 13.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.