# Number Theory problem

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jun 26th 2010, 02:56 PM
shostakovich
Number Theory problem
hello number theorists ,

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

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

• Jun 26th 2010, 03:21 PM
chiph588@
Quote:

Originally Posted by shostakovich
hello number theorists ,

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

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

What is this problem for? The context of the problem may make it easier to solve.
• Jun 26th 2010, 03:51 PM
shostakovich
well , the original problem says : let $A$ a set of prime numbers , such that for all finite subset $S$ of $A$ , and $S<> A$, we have: all prime divisors of : $(\prod_ {p\in S}p )-1$ are also in $A$, Show that $A$ is the set of prime numbers
I had the idea to use induction and the lemma above
• Jun 26th 2010, 04:25 PM
Also sprach Zarathustra
I find similarity between the problems... Euclid's Proof of the Infinitude of Primes (c. 300 BC)
• Jun 26th 2010, 06:24 PM
chiph588@
Quote:

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

What does $S<>A$ mean?
• Jun 27th 2010, 08:35 PM
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
• Jun 27th 2010, 10:25 PM
chiph588@
Quote:

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.
• Jun 27th 2010, 10:53 PM
Bacterius
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 :)
• Jun 28th 2010, 11:45 AM
jamix
The original conjecture sounds wrong. For instance, if you take p = 5, Then P = {3}, which implies 5 | 3 - 1.
• Jun 28th 2010, 12:46 PM
shostakovich
TO Jamix , what about $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 $S= \prod_{p\in A}p$, let $a\in A$, by conditions $\frac{S}{a} -1$ has all prime divisors in A, but $\frac{S}{a}-1$ is prime with each element of $A$ Except $a$, we conclude that $\frac{S}{a}-1= a^k$ for some positive integer $k$ , that is $S= a^{k+1}+a$,

now it is easy to prove that $2,3,5$ are in A , in particuler $S= 2^{a}+2$ and $S= 3^{b}+3$ , for some positive integers $a,b$ since $S \geq 2*3*5= 30,$ we conclude that $a \geq 4$, looking $mod 16$ we get $S= 2 [16]$ that is $3^b=-1 [16]$ 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 $F_q$, we can suppose that this residue isn't 0 , let $c_1,c_2,.......c_{q-1}$ those primes , hence by Fermat little theorem , we have $c_1c_2....c_{q-1}=1[q]$ and we are done (Happy)
• Jun 28th 2010, 01:24 PM
chiph588@
I wonder if the original lemma you posted is false or not.
• Jun 28th 2010, 03:03 PM
jamix
Quote:

Originally Posted by shostakovich
TO Jamix , what about $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 $S= \prod_{p\in A}p$, let $a\in A$,

I thought $S$ was suppose to be a finite subset of $A$ which contains only primes?

In any case, if you define $S$ as you did above, couldn't you just conclude that $A$ must have infinitely many primes based on the fact that $S - 1$ doesn't share any primes in common with $A$?
• Jun 28th 2010, 03:41 PM
Defunkt
Quote:

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

2 is a prime indeed.
• Jun 28th 2010, 04:22 PM
jamix
I made a mistake, but that doesn't have anything to do with my last post.
• Jun 29th 2010, 12:57 AM
shostakovich
Quote:

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

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

WEll read carefully the conditions , S is different of A (Wink)

to chiph588@ : I'm not sure , may be some one good with programming can verify big value with computer !
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last