215 views

Consider numbers greater than one that satisfy the following properties:

1. They have no repeated prime factors;
2. For all primes $p \geq 2$, $p$ divides the number if and only if $p − 1$ divides the number.

The number of such numbers is

1. $0$.
2. $5$.
3. $100$.
4. Infinite.
5. None of the above.
| 215 views

The prime factors of $30$ are $2,3,5$, so it satisfies the 1st constraint.

However, $\matrix{ (2-1) & \rm divides & 30 & \color{green}\checkmark\\ (3-1) & \rm divides & 30 & \color{green}\checkmark\\ (5-1) & \rm divides & 30 & \color{red}\times\\ }$ and thus it doesn't satisfy the 2nd constraint.
One can prove that for $n$ to satisfy these properties, $n=p(p−1)$ for some prime $p$ and that $(p−1)$ satisfies the properties too.

Some examples of the numbers that satisfy both constraints are:
\begin{align} &2\\ 2 \times 3 = &6\\ 6 \times 7 = &42\\ 42 \times 43 = &1806 \end{align}Now $1807$ is not a prime and hence breaks the sequence. So, number of such numbers is $4.$

by Boss (22.7k points)
selected by
0

ok u mean to say 1806 *1807=3263442, now it will going to be very large. now am I right sir?plz tell

0
1806 * 1807. But 1807 = 13 * 139, would it cause any problem?
0
then  p=1087 is not a prime no, then p is not a prime number which (b) told actually.right?
+1
1807 is not a prime number- but how is condition b violated for 1806 * 1807? Because 13 is a prime number which divides this but 13-1=12 does not.

So, we only got 4 numbers. Any more possible? Really hard one during exam :)
+2
Yes, kinda lengthy. One can prove that for $n$ to satisfy these properties, $n = p (p-1)$ for some prime $p$ and that $(p-1)$ satisfies the properties too.

Once that is achieved, it is a simple matter of noticing that $1807$ is not a prime and hence breaks the sequence.
0
okay, It is going to check longest chain ,right?

But upto how many times should I check , as there is no upper limit ? because there will be always a chance of error in result. Am I right sir?
+4
Well, answer is 4. And the reason is told by Pragy. This is the only chain possible and it goes from 2, 6, 42. 1806. After this 3263442 comes and it doesn't satisfy the second constraint and hence we got the answer. But to try this for first time in exam is tricky. I guess for these questions smart people should get 0 and not negative :)
–1 vote
(a) no repeated prime number.So it can be{2,3,5,6(2*3 so no repeatation of prime in 6),7,11, 13,15,..........,}

(b) it can be (2,3)=6

(6,7)=42

...............

(10,11)=110

So, we can say, as prime no is infinite, answer will be (d)infinite
by Veteran (117k points)
edited by

2