what natural numbers are less than or equal to 7 that are relatively prime?

Trouble

Permit $\,n > 6\,$ be an integer and $\,a_{1},a_{2},\cdots ,a_{k}\,$ be all the natural numbers less than $n$ and relatively prime number to $n$ . If $a_{2} - a_{1} = a_{3} - a_{2} = \cdots = a_{k} - a_{k - 1} > 0,$ prove that $\,n\,$ must be either a prime or a ability of $\,2$ .

Solution 1

We utilize Bertrand's Postulate: for $u\ge 2$ is a positive integer, there is a prime number in the interval $(u,2u)$ .

Clearly, $a_2$ must be equal to the smallest prime number $p$ which does not divide $n$ . If $p=2$ , then $n$ is a prime since the common deviation $a_{i+1}-a_i$ is equal to $1$ , i.east. all positive integers less than $n$ are coprime to $n$ . If, on the ther hand, $p=3$ , we find $n$ to exist a power of $2$ : the positive integers less than $n$ and coprime to it are precisely the odd ones. We may thus assume that $p\ge 5$ . Furthermore, since $n>6$ , the positive integers less than $n$ and coprime to it cannot be $a_1,a_2$ solitary, i.e. $k=\varphi(n)\ge 3$ .

Past Bertrand'southward Postulate, the largest prime less than $p$ is strictly larger than $\frac{p-1}2$ , and so it cannot divide $p-1$ . We will denote this prime by $q$ . We know that $q|n$ . It'south easy to check that for $p\le 31$ there is a prime $r$ strictly between $a_2=p,\ a_3=2p-1$ . $rq|n$ , then, in detail, $pq<rq\le n$ . On the other hand, if $p>32$ , the two largest primes $r_1<r_2$ which are smaller than $q$ satisfy $r_2\ge\frac p4,\ r_1\ge\frac{r_2}2\ge\frac p8$ (once more, Bertrand's Postulate), so $pq<\frac{p^2}{32}q\le r_1r_2q\le n$ so, one time over again, nosotros have $pq<n$ (this is what I wanted to evidence here).

Now, $q\not|p-1$ , and all the numbers $1,1+p-1,\ldots,1+(q-1)(p-1)$ are smaller than $n$ (they are smaller than $pq$ , which is smaller than $n$ , co-ordinate to the paragraph above). I of these numbers, however, must exist divisible by $q|n$ . Since our hypothesis tells u.s.a. that all of them must be coprime to $n$ , nosotros have a contradiction.

This solution was posted and copyrighted by grobber. The original thread for this trouble can be found here: [1]

Solution 2

Let $d=a_{i+1}-a_i$ . So nosotros have $a_i=1_1+d(i-1)=1+d(i-1)$ . Since $\gcd(n-1,n)=1$ , and then $n-1$ is the largest positive integer smaller than $n$ and co-prime to $n$ . Thus, $a_k=n-1$ and $1+d(k-1)=n-1$ which shows $d(k-1)=n-2$ and so $d$ divides $n-2$ . We make ii cases. Case i: $n$ is odd. Then $\gcd(n-2,n)=1$ . So, every divisor of $n-2$ is co-prime to $n$ also, and so is $d$ . Thus, there is a $j$ such that $d=a_j=1+d(j-1)$ which implies $d|1$ . Therefore, in this case, $d=1$ and we easily notice that all numbers less than $n$ are co-prime to $n$ , so $n$ must be a prime number. Case 2: $n$ is even. But and then $\gcd(n-2,n)=2$ and also $d=1$ is ruled out. And so $d>1$ . Say, $n=2l$ . Then, $d$ divides $2(l-1)$ . If $d$ is odd, $d|l$ and $d|l-1$ forcing $d|1$ , contradiction! And so, $d=2s$ with $s|l-1$ . If $l=2r+1$ for some $r$ , then $\gcd(r,n)=1$ . And so, once more $r=1+d(j-1$ for a $j$ . If $s$ is odd, then $s|r$ and thus, $s|1$ . Similarly, we discover that actually $d|2$ must occur. Nosotros finally have, $d=2$ . Just then all odd numbers less than $n$ are co-prime to $n$ . Then, $n$ does not take any odd factor i.due east. $n=2^k$ for some $k\in\mathbb N$ .

This solution was posted and copyrighted by ngv. The original thread for this problem can be constitute hither: [two]

Solution 3

Nosotros use Bonse's Inequality: $p_{m+1}^2 < p_1p_2\cdots p_m$ , for all $m \ge 4$ , $p_1 = 2$ .

Let $p$ denote the smallest prime which does not divide $n$ .

Example 1) $p = 2$ . This implies $n$ is a prime. Case 2) $p = 3$ . This implies $n = 2^k$ for some $k \in \mathbb{N}$ . Case iii) $p = 5$ . Since $n > 6$ , we have that $n > 9$ . Therefore $a_3 = 9$ , but $\gcd (n, 9) > 1$ . Case 4) $p \ge 7$ . Write $n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ . We have $(p - 2)^2 < p_1p_2\cdots p_k \le n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ . Hence $(p-2)^2 = a_i$ , a contradiction since $\gcd(p-2, n) > 1$ .

This solution was posted and copyrighted by SFScoreLow. The original thread for this trouble can be constitute hither: [3]

Solution 4

Clearly, $a_1 = 1$ . Now permit $p$ be the smallest prime number which is non a divisor of $n$ . Hence, $a_2 = p$ , and the mutual divergence $d = p-1$ . Find that since $a_k = n-1$ , we take that $d \mid a_k - a_1$ , or $p - 1 \mid a_k - a_1 = n-2$ . This ways that all prime number factors of $p-1$ are prime factors of $n-2$ . Notwithstanding, due to the minimality of $p$ , all primes factors of $p-1$ are prime factors of $n$ . By the Euclidean algorithm, the only prime factors of $p-1$ are $2$ , and then $p = 2^{2^k} + 1$ or $p = 2$ , by the theory of Fermat primes. We will now do casework on $p$ .

Instance 1: $p = 2$ This case is relatively easy. $a_2 = 2$ , then all numbers less than $n$ must be relatively prime to $n$ . Nevertheless, if $n = pq$ , where $p > 1$ and $q > 1$ , observe that $p$ is not relatively prime to $n$ , so $n$ must be prime for this example to work.

Case ii: $k = 0$ and $p = 3$ . This case is somewhat tricky. Notice that $n$ is even. Since $a_2 = 3$ , we take that all numbers less than $n$ which are odd are relatively prime number to $n$ . Still, if $n$ has a odd divisor $p > 1$ , clearly $p$ is not relatively prime to $n$ , then $n$ must exist a power of two.

Case 3: $k \ge 1$ . Note that $3$ must be a divisor of $n$ , so $a_k$ cannot exist a multiple of $3$ for any $k$ . I will contradict this argument. First, I merits that $k = \phi(n) > 2$ for all integers $n > 6$ . $\phi{n} = 1$ is piddling, and then let me show that $\phi(n) = 2$ has just solutions less than or equal to $6$ . Since $\phi$ is a multiplicative function, observe that $n$ cannot exist a multiple of a prime greater than $3$ , considering for such primes $p$ we have that $\phi(p^k) = (p-1)p^{k-1} \ge p-1 > 2$ , which is contradiction. Hence, $n$ is just composed of factors of $2$ and $3$ . If information technology divides both, and is of the form $2^m 3^n$ for $m$ and $n$ positive, nosotros get that nosotros demand $2^{m} 3^{n-1} = 2$ , and so $n = 1$ and $m = 1$ in this case. If it is of the form $n = 2^k$ , nosotros get $k = 2$ . And if it is of the course $3^k$ , we get $k = 1$ . $3$ , $4$ , and $6$ are all less than or equal to $6$ , so $\phi(n) > 2$ . Now we're nearly washed. Since $k > 2$ , the number $a_3 = 2p-1$ must be in this sequence. However, $a_3 = 2p-1$ is of the grade $2^{2^n+1} + 1$ , which is a multiple of $3$ , and we have contradiction, so we are washed.

This solution was posted and copyrighted by va2010. The original thread for this problem tin can be constitute here: [iv]

Solution 5

Clearly that $a_1=1$ . Allow $a_{i+1}-a_i = d \; (1 \le i \le \varphi(n)-1)$ then $a_{i}=(i-1)d+1 \; \; (1 \le i \le \varphi(n)). \qquad (1)$ We can see that if $n$ is a prime and then $n$ satisfies the status. Nosotros consider the case when $n$ is a composite number. Permit $p$ be the smallest prime number divisor of $n$ then $p \le \sqrt{n}$ . Note that $\varphi (n) > \sqrt{n} \ge p$ for all prime number $n>6$ since $p_i^{k_i}-p_i^{k_i-1} \ge p_i^{k_i/2}$ for all $p \ge 3$ . Therefore, if $p \nmid d$ so there will exists $1 \le i \le \varphi(n)$ such that $(i-1)d \equiv -1 \pmod{p}$ or $p \mid a_i$ , a contradiction since $\gcd (a_i,n)=1$ . Thus, $p \mid d$ . We consider two cases:

If $d \ge 2p$ and then $p+1 \ne a_i \; (1 \le i \le \varphi(n))$ . Hence, $\gcd (p+1,n)>1$ . This means there exists a prime $q>p \ge 2$ such that $q \mid p+1$ . Since $q>p$ then nosotros get $q=p+1$ or $p=2,q=3$ , a contradiction since $n>6$ . Thus, $d <2p$ or $d=p$ .

If $p=d=2$ then all odd numbers $a_i \le n$ are relatively prime number to $n$ . This can only happen when $n=2^x \; (x \in \mathbb{N})$ .

If $p=d >3$ and so $p+3 \ne a_i \; \forall 1 \le i \le \varphi(n)$ since $a_i \equiv 1 \pmod{p} \; \forall 1 \le i \le \varphi(n)$ . Thus, $\gcd (p+3,n)>1$ or there exist a prime number $q>p>3$ such that $q \mid p+3$ . Note that $2 \mid p+3$ and then $q \le \tfrac{p+three}{two}<p$ , a contradiction.