No Other Prime Must Divide It

For all n Z , n \in \mathbb{Z}, let ω ( n ) \omega (n) denote the number of distinct prime divisors of n . n. Find the sum of all primes p p such that ω ( ( p 1 ) ! + 1 ) = 1. \omega ((p-1)!+1) = 1.

Details and assumptions

  • As an explicit example, since 100 = 2 2 × 5 2 100= 2^2 \times 5^2 has two distinct prime divisors ( 2 2 and 5 5 ), ω ( 100 ) = 2. \omega (100) = 2.


The answer is 10.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Kishlaya Jaiswal
Jun 12, 2014

For ω ( n ) \omega(n) to be equal to 1 1 , we need n n to be equal to q r q^r where q q is any prime no. and r ϵ N r \epsilon N .

Therefore, we need ( p 1 ) ! + 1 = q r (p-1)!+1 = q^r

But, observe that -

( p 1 ) ! + 1 0 ( m o d p ) (p-1)!+1 \equiv 0 \pmod{p} (By Wilson Theorem)

( p 1 ) ! + 1 = p m \Rightarrow (p-1)!+1 = pm (for some m m )

But, again remember that ( p 1 ) ! + 1 = q r (p-1)!+1 = q^r .

This suggests that m m should be equal to p k 1 p^{k-1} for some arbitrary k k which enables us to write

( p 1 ) ! + 1 = p k (p-1)!+1 = p^k

( p 1 ) ! = p k 1 \Rightarrow (p-1)! = p^k-1

Now, we suspect that the solutions to the above equation are 2 , 3 , 5 {2,3,5} only.

This can easily be proved by considering the following inequality for p 7 p \geq 7

( p 1 ) 2 ( p 1 ) ! (p-1)^2|(p-1)!

( p 1 ) 2 p k 1 \Rightarrow (p-1)^2|p^k-1

p 1 1 + p + p 2 + p k 1 \Rightarrow p-1|1+p+p^2+\ldots p^{k-1}

p k 1 > ( p 1 ) ! \Rightarrow p^k-1 > (p-1)!

Thus, the only solutions are 2 , 3 , 5 {2,3,5} which sum up to 2 + 3 + 5 = 10 2+3+5 = \boxed{10}

may I ask where ( p 1 ) 2 ( p 1 ) ! (p-1)^{2} | (p-1)! come from, still a bit confused here :/

Chalvin Rmc - 6 years, 11 months ago

Log in to reply

For composite p 6 p\leq 6 , we have p ( p 1 ) ! p|(p-1)! . A proof can be seen here

For primes p 7 p\leq7 , we thus have p 1 p-1 being composite and using the previous theorem we have p 1 ( p 2 ) ! p-1|(p-2)! and consequently ( p 1 ) 2 ( p 1 ) ! (p-1)^2|(p-1)!

Jared Low - 6 years, 2 months ago

wilson and liouville

can you tell us the liouville theorem you're talking about? There are a lot of different theorems proved by him...

mathh mathh - 6 years, 9 months ago
Krishna Ar
Jun 11, 2014

Sorry, I will post a better solution involving proper methods later. For now, I solved this question by hit and trial. We see that for 2 2 , 3 3 and 5 5 ...the answers are 2 2 , 3 3 and 25 25 respectively which have exactly one prime divisor (unique). Verifying for 7 7 and 11 11 , we find that they don't work. Thus answer= 2 + 3 + 5 = 10 2+3+5= {10}

I tried Wilson's theorem.

Log in to reply

How can you prove that primes greater than or equal to 7 7 will give a value greater than 1 1 .

Log in to reply

Sorry! I will try solving it properly and edit my solution later as mentioned above.

Krishna Ar - 7 years ago

Log in to reply

@Krishna Ar The proof is given by inequality: for p>5, ( p 1 ) 2 ( p 1 ) ! = p m 1 (p-1)^2|(p-1)!=p^{m}-1

Thus, p 1 m p-1|m and then we will get p m 1 > ( p 1 ) ! p^m-1>(p-1)!

That leaves p=2,3,5

Bogdan Simeonov - 7 years ago

Log in to reply

@Bogdan Simeonov Wow. That proof was niceee! ^_^. I came up with something different and was no wonder stuck on it :(. Do you attend some special school? I hear Bulgarians are good at math ;)

Krishna Ar - 7 years ago

Log in to reply

@Krishna Ar Well, there are many countries on the Balkan Peninsula which are great at math, such as Romania.I guess we are somewhat good.I study at a school with a math profile, but I learn mostly by going to the Balkan Olympiad lectures we are having right now and books, Brilliant , the Internet etc.Where did you hear that Bulgarians were good at math?I'm curious :D

Bogdan Simeonov - 7 years ago

Log in to reply

@Bogdan Simeonov Well, yes- I actually thought that you were mathematically motivated because you did answer a lot of good questions on this site. And w.r.t Bulgarians- I think Its because of your firstname. I see many math authors - Bogdan Enescu and the like with the same first name. What are those lectures? Are they held only in Bulgaria?

Krishna Ar - 7 years ago

Log in to reply

@Krishna Ar The lectures are on a training camp for the Balkan Olympiad.It's like IMO training, but for the Balkan MO.Every country which participates in an MO has these training camps where students solve problems.Also, Bogdan Enescu is from Romania.

Bogdan Simeonov - 7 years ago

Log in to reply

@Bogdan Simeonov Wow! We never have such exposure :(

Krishna Ar - 7 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...