Divisibility by primes

Question

Suppose that $n$ is a natural number, $n \ge 2$, and $n$ satisfies:

1. For each prime divisor $p$ of $n$, $p^2$ does not divide n.
2. If $p$ is prime, $p$ divides $n$ if and only if $(p − 1)$ divides $n$.

Compute $n$.

---

$p-1$, $p$ are both primes if that is $2$ and $3$ so

$p_0=2$

$p_1=p_0+1=3$

$p_2=p_0p_1+1=7$

$p_3=p_0p_1p_2+1=43$

$p_4=1807$

I am kind of lost what to do next. Thank you very much

Answer 1

Hint: In addition to $2\cdot3\cdot7\cdot43+1=1807$, you need to consider whether $2\cdot43+1$, $2\cdot3\cdot43+1$ and $2\cdot7\cdot43+1$ are prime as well.

Answer 2

From $1\mid n$, we conclude $2\mid n$, then $3\mid n$, then $7\mid n$. On the other hand $5\nmid n$ as $4\nmid n$, and then $11,13,17,19,23\nmid n$, and so on. We can determine the list of prime divisors of $n$ by enumerating $p=2,3,5,7,\ldots$ and for each prime test if $p-1$ divides the product of all primes accepted so far. We can (and must) stop as soon as $p$ grows larger than the product of all accepted primes plus 1.

Instead of enumerating the primes, we could check all possible products of primes found so far if their successor is prime. This way we start with no prime at all, the empty product is $1$, hence we check if $2$ is prime - it is, and we add $2$ to our list. The new factor $2$ produces one new product, $2$ itself; we check if $2+1$ is prime - it is, we get $3$ as a new factor. The new factor $3$ produces two new products, $3$ and $6$; only $6+1$ is prime. The new factor $7$ produces four new products, $7, 14, 21, 42$; only $42+1$ is prime. The new factor $43$ produces eight new products, $43, 86,\ldots, 1806$; as adding $1$ produces no primes, we are done.

$$ n=2\cdot 3\cdot 7\cdot 43 = 1806.$$

Answer 3

I think the answer is : you define $P_k$ the sequence of prime numbers such as :

$P_{k} = 1 + P_1*P_2*..*P_{k-1}, with $ $ P_1=2$

And n can be any product such as $P_1*P_2*P_3*...*P_k$, for any k. That way the $P_k -1 $ are criss-crossed with the $P_1,P_2,..P_{k-1}$ and the conditions hold. The prime numbers must follow each other and start from the beginning.$ P_3*P_4*P_5 $ is not correct for instance.

Examples: $P_1=2$ , $ n=2 $

$P_1=2, P_2=3$ , $ n=6$

$P_1=2, P_2=3, P_3=7$ , $ n=42 $ Etc...

Edit:the answer is uncomplete, but I think this works:

First you prove that if you write n as: $n=P_1*P_2*...*P_k$, with $P_k$ all distincts

then they are linked with a relation: $P_{k+1} = 1 + P_1*P_2*...*P_k$ , with $P_1=2 $

Now we don't know yet if all $P_k$ are prime numbers, we just know that if $P_k$ divides n, then he is part of this sequence and if a $P_j$ is not a prime number then the sequence of the prime divisors of n stops at $P_{j-1}$ because the conditions are no longer verified ($P_j$ not prime number, $P_j=p*q$, with p and q not part of the sequence $(P_k)$ for divisibility reasons)

$P_5 = 1807= 13*139 $

--> the sequence stops at $P_4 $

so Solutions= {2,6,42,1806}