A 15

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

A 15

G H J

Reveal topic tags

least common multiple

Divisibility Theory

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#1 h May 25, 2007, 12:24 AM • 3 Y

Y by narutomath96, Adventure10, Mango247

Suppose that $k \ge 2$ and $n_{1}, n_{2}, \cdots, n_{k}\ge 1$ be natural numbers having the property $n_{2}\; \vert \; 2^{n_{1}}-1, n_{3}\; \vert \; 2^{n_{2}}-1, \cdots, n_{k}\; \vert \; 2^{n_{k-1}}-1, n_{1}\; \vert \; 2^{n_{k}}-1.$ Show that $n_{1}=n_{2}=\cdots=n_{k}=1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7579 posts

ZetaX

#2 h May 25, 2007, 12:24 AM • 7 Y

Y by narutomath96, Wizard_32, naw.ngs, Adventure10, Mango247, and 2 other users

If one $n_i$ is $1$ , then all have to be $1$ . So lets assume that all are $\neq 1$ .

Let $i \in \{1,2,...,k\}$ always and define $n_{k+1} :=n_1$ (indices are seen $\mod k$ ).
Let $p_i$ be the smallest prime divisor of $n_i>1$ and let $o_i$ be the order of $2 \mod p_i$ and $q_i$ be the smallest prime factor of $o_i$ .
We have $o_i|n_{i+1}$ by standard facts on orders, giving $p_{i+1} \leq q_i$ . We also have $o_i|p_i-1$ , thus $q_i \leq p_i-1$ . As a result, $p_{i+1} \leq q_i \leq p_i-1 < p_i$ .
But this gives $p_1 < p_2 < ... < p_k <p_1$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1313 posts

TTsphn

#3 h Oct 26, 2007, 9:10 AM • 9 Y

Y by narutomath96, Wizard_32, Kamran011, puntre, aves, Adventure10, and 3 other users

Here is an other method.
$x = lcm(n_1,..,n_k)$
So $n_i|2^x - 1,\forall i = 1,..,k$
Imply that $x|2^x - 1$
So $x = 1$ (tradition!)
http://www.mathlinks.ro/Forum/viewtopic.php?p=849217#849217

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

628 posts

maxal

#4 h Apr 27, 2010, 5:43 PM • 2 Y

Y by Adventure10, Mango247

See also http://www.artofproblemsolving.com/Forum/viewtopic.php?p=420694#p420694

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

anonymouslonely

1142 posts

anonymouslonely

#5 h Sep 24, 2011, 8:16 AM • 2 Y

Y by Adventure10, Mango247

TTsphn wrote:

Here is an other method.
$x = lcm(n_1,..,n_k)$
So $n_i|2^x - 1,\forall i = 1,..,k$
Imply that $x|2^x - 1$
So $x = 1$ (tradition!)
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=849217#849217

but this only imply $x|2^{x}-1$ ...can you explain how did you obtain $n_{i}|2^{x}-1$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#6 h Sep 24, 2011, 8:46 AM • 8 Y

Y by narutomath96, FlakeLCR, JasperL, Tawan, Kamran011, vsamc, Adventure10, Mango247

It has been denoted $x = \textrm{lcm}(n_1,\ldots,n_k)$ .
It follows $n_i \mid 2^{n_{i-1}} - 1 \mid 2^x - 1$ , for all $i = 1,\ldots,k$ , where $n_0 := n_k$ (indices are taken modulo $k$ ), since if $a \mid b$ , then $2^a - 1 \mid 2^b - 1$ .
Therefore $x \mid 2^x - 1$ .
So $x = 1$ (by a well known result, whose proof also uses the least prime dividing $x$ , as some method above).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

326 posts

#7 h May 15, 2012, 3:01 AM • 2 Y

Y by Adventure10, Mango247

Simply consider the smallest prime $p$ that divides one of the $n_i$ . Then we get a smallest prime, leading to a contradiction. Thus there is no prime $p$ that divides any of the $n_i$ giving the desired conclusion.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#8 h Jun 9, 2016, 8:01 AM • 2 Y

Y by Adventure10, Mango247

Let the solution least solution be $(n_{1},n_{2},...,n_{k})$ for some $k$ .Let $d_{i}$ be the order of $2$ modulo $n_{i}$ .Now $(d_{1},d_{2},...,d_{k})$ will be a smaller solution of unless $n_{2}$
$n_{2}$ is the order of $2$ modulo of $n_{1}$ and like that.Therefore $n_{1}$ divides $\phi(n_{2})$ .Therefore $n_{1}$ is less than or equal to $n_{2}$ .Similarly $n_{2}$ is less than or equal to $n_{3}$ ,....., $n_{k}$ is less than or equal to $n_{1}$ .Therefore all the numbers must be equal and now $n$ divides $2^{n}-1$ only when $n=1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

300 posts

hansu

#9 h Jan 3, 2019, 4:57 PM • 4 Y

Y by AlastorMoody, khan.academy, Adventure10, Mango247

Here I post another slightly different solution to this beautiful problem.

Peter wrote:

Suppose that $k \ge 2$ and $n_{1}, n_{2}, \cdots, n_{k}\ge 1$ be natural numbers having the property $n_{2}\; \vert \; 2^{n_{1}}-1, n_{3}\; \vert \; 2^{n_{2}}-1, \cdots, n_{k}\; \vert \; 2^{n_{k-1}}-1, n_{1}\; \vert \; 2^{n_{k}}-1.$ Show that $n_{1}=n_{2}=\cdots=n_{k}=1$ .

Consider the following set
$S=\{(n_1,n_2,\ldots,n_k): n_i\ne 1 \text{for any}~ 1\le i\le k ~\text{and}~ n_{i+1}\mid 2^{n_i}-1~\text{for every i}, \text{where all the indices are taken modulo k}\}$
Now consider the sum $(n_1+n_2+\ldots+n_k)$ . Choose the $n$ -tuple from $S$ which has the least sum.
For every $i$ , we know that
$n_i\mid 2^{\phi(n_i)}-1$ Hence we have that
$n_i\mid 2^{d_{i-1}}-1$ where $d_{i-1}=\gcd(n_{i-1},\phi(n_i))$ . But we can also say that $d_{i+1}\mid 2^{d_i}-1$ .

Now if $d_i<n_{i-1}$ for some $i$ , then we can do the following transformation
$(n_1,n_2,\ldots,n_k)\longrightarrow (n_1,n_2,\ldots,n_{i-1},d_i,n_{i+1},\ldots,n_k)$ But note that the new tuple has sum smaller than the "mother tuple", a contradiction.

Otherwise if $d_{i}=n_{i-1}$ for all $i$ . Then we have $n_i\mid \phi(n_{i+1})\Longrightarrow n_i\le \phi(n_{i+1}) < n_{i+1}$ . A contradiction! $~\blacksquare$

This post has been edited 3 times. Last edited by hansu, May 1, 2019, 9:32 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

328 posts

#10 h Apr 16, 2020, 9:28 AM

Y by

if one of $n_i$ s happen to be $1$ then all of them will equal to one. now suppose $p$ is the smallest prime factor of $\prod n_i$

and $p|n_k$ and because $n_k | 2^{n_{k-1}} -1 \implies p|2^{n_{k-1}} -1 \implies 2^{n_{k-1}} \equiv 1 \mod p$

and now as $n_{k-1}$ doesn't have any prime factor less that $p$ so it's co-prime with $p-1$ and because $2^{p-1} \equiv 1 \mod p$

then $p$ must be $1$ which a contradiction which means we can't chose smallest prime factor of $\prod n_i \implies \prod n_i =1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

243 posts

pie854

#11 h Sep 17, 2024, 8:32 PM

Y by

Say $n_m=1$ then it follows that $n_{m+1}=n_{m+2}=\dots=n_k=n_1=1$ and so $n_1=n_2=\dots=n_{m-1}=1$ too. Now suppose none of them is $1$ . Let $p_i$ be the smallest prime divisor of $n_i$ . Then $p_i \mid 2^{n_{i-1}}-1 \implies \text{ord}_{p_i} (2) \mid n_{i-1},$ so $p_{i-1} < \text{ord}_{p_i} (2) < p_i \implies p_1<p_2<\dots<p_k<p_1,$ a contradiction.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a