# Thread: Number Theory problem

1. ## Number Theory problem

hello number theorists ,

I'm beginner and I have troubles with this lemma which i belive it is true ,

let $\displaystyle p$ a prime number greater than $\displaystyle$3, and let $\displaystyle P$ be the set of primes less than $\displaystyle p$, show that there exist $\displaystyle p_1 , p_2 ... ,p_n$ from $\displaystyle P$, such that $\displaystyle p$ divides $\displaystyle \prod_{i=1}^{i=n} p_i -1$

Thanks in ADvance 2. Originally Posted by shostakovich hello number theorists ,

I'm beginner and I have troubles with this lemma which i belive it is true ,

let $\displaystyle p$ a prime number greater than $\displaystyle 3$, and let $\displaystyle P$ be the set of primes less than $\displaystyle p$, show that there exist $\displaystyle p_1 , p_2 ... ,p_n$ from $\displaystyle P$, such that $\displaystyle p$ divides $\displaystyle \prod_{i=1}^{i=n} p_i -1$

Thanks in Advance What is this problem for? The context of the problem may make it easier to solve.

3. well , the original problem says : let $\displaystyle A$ a set of prime numbers , such that for all finite subset $\displaystyle S$ of $\displaystyle A$ , and $\displaystyle S<> A$, we have: all prime divisors of : $\displaystyle (\prod_ {p\in S}p )-1$ are also in $\displaystyle A$, Show that $\displaystyle A$ is the set of prime numbers
I had the idea to use induction and the lemma above

I find similarity between the problems... Euclid's Proof of the Infinitude of Primes (c. 300 BC)

5. Originally Posted by shostakovich well , the original problem says : let $\displaystyle A$ a set of prime numbers , such that for all finite subset $\displaystyle S$ of $\displaystyle A$ , and $\displaystyle S<> A$, we have: all prime divisors of : $\displaystyle (\prod_ {p\in S}p )-1$ are also in $\displaystyle A$, Show that $\displaystyle A$ is the set of prime numbers
I had the idea to use induction and the lemma above
What does $\displaystyle S<>A$ mean?

6. well it means that S is different of A, sorry I'm not good at latex

Actually I found the solution in the internet , it is very elegant , I will share it here as soon as I can

7. Originally Posted by shostakovich well it means that S is different of A, sorry I'm not good at latex

Actually I found the solution in the internet , it is very elegant , I will share it here as soon as I can
Can't wait! This problem is stumping me for some reason.

8. Scratch that I didn't see your next post. Hang on ...
Yeah, I like this problem. I'll be thinking about it, feel free to post the solution you found 9. The original conjecture sounds wrong. For instance, if you take p = 5, Then P = {3}, which implies 5 | 3 - 1.

10. TO Jamix , what about $\displaystyle 2*3-1$? , anyway here is the solution

( I apologize , I forgot to mention that A contains at least 3 elements )

First of all we shall prove that A is infinite , indeed suppose it is finite for sake of contradiction, consider $\displaystyle S= \prod_{p\in A}p$, let $\displaystyle a\in A$, by conditions $\displaystyle \frac{S}{a} -1$ has all prime divisors in A, but $\displaystyle \frac{S}{a}-1$ is prime with each element of $\displaystyle A$ Except $\displaystyle a$, we conclude that $\displaystyle \frac{S}{a}-1= a^k$ for some positive integer $\displaystyle k$ , that is $\displaystyle S= a^{k+1}+a$,

now it is easy to prove that $\displaystyle 2,3,5$ are in A , in particuler $\displaystyle S= 2^{a}+2$ and $\displaystyle S= 3^{b}+3$ , for some positive integers $\displaystyle a,b$ since $\displaystyle S \geq 2*3*5= 30,$ we conclude that $\displaystyle a \geq 4$, looking $\displaystyle mod 16$ we get $\displaystyle S= 2 $ that is $\displaystyle 3^b=-1 $ which is is a contradiction ,

let q a prime number , since A is infinite , there exist at least q-1 prime number which have the same residue in $\displaystyle F_q$, we can suppose that this residue isn't 0 , let $\displaystyle c_1,c_2,.......c_{q-1}$ those primes , hence by Fermat little theorem , we have $\displaystyle c_1c_2....c_{q-1}=1[q]$ and we are done 11. I wonder if the original lemma you posted is false or not.

12. Originally Posted by shostakovich TO Jamix , what about $\displaystyle 2*3-1$? , anyway here is the solution

( I apologize , I forgot to mention that A contains at least 3 elements )

First of all we shall prove that A is infinite , indeed suppose it is finite for sake of contradiction, consider $\displaystyle S= \prod_{p\in A}p$, let $\displaystyle a\in A$,
I thought $\displaystyle S$ was suppose to be a finite subset of $\displaystyle A$ which contains only primes?

In any case, if you define $\displaystyle S$ as you did above, couldn't you just conclude that $\displaystyle A$ must have infinitely many primes based on the fact that $\displaystyle S - 1$ doesn't share any primes in common with $\displaystyle A$?

13. Originally Posted by jamix I thought $\displaystyle S$ was suppose to be a finite subset of $\displaystyle A$ which contains only primes?
2 is a prime indeed.

14. I made a mistake, but that doesn't have anything to do with my last post.

15. Originally Posted by jamix I thought $\displaystyle S$ was suppose to be a finite subset of $\displaystyle A$ which contains only primes?

In any case, if you define $\displaystyle S$ as you did above, couldn't you just conclude that $\displaystyle A$ must have infinitely many primes based on the fact that $\displaystyle S - 1$ doesn't share any primes in common with $\displaystyle A$?
WEll read carefully the conditions , S is different of A to chiph588@ : I'm not sure , may be some one good with programming can verify big value with computer !

#### Search Tags

number, problem, theory 