Let n1,n2n_1, n_2 integers. Show that if

n1|2n2−1n2|2n1−1n_1|2^{n_2}-1 \, \, n_2|2^{n_1}-1

then n1=n2=1n_1=n_2=1.

I want a little hint for this problem. I tried to use the proof of

There is not n>1n>1 such that n|2n−1n|2^n-1

but I got nothing.

=================

=================

1 Answer

1

=================

Assume that both n1,n2n_1,n_2 are odd and >1>1. Let p1p_1 be the smallest prime divisor of n1n_1, p2p_2 the smallest prime divisor of n2n_2. Then p1p_1 divides both 2n2−12^{n_2}-1 and 2p1−1−12^{p_1-1}-1, hence p1p_1 divides 2gcd(n2,p1−1)−12^{\gcd(n_2,p_1-1)}-1. Similarly, p2p_2 divides 2gcd(n1,p2−1)−12^{\gcd(n_1,p_2-1)}-1. If p2≤p1p_2\leq p_1, p2∣2gcd(n1,p2−1)−1p_2\mid 2^{\gcd(n_1,p_2-1)}-1 implies p2=1p_2=1, contradiction. Similarly, if p1≤p2p_1\leq p_2, p1∣2gcd(n2,p1−1)−1p_1\mid 2^{\gcd(n_2,p_1-1)}-1 implies p1=1p_1=1, contradiction.

This is exactly the proof you probably mentioned, with a minor twist.

I get too close. Thanks

– YTS

Oct 21 at 0:16

You are missing something, why does p1p_1 divide gcd(n2,p1−1)gcd(n_2,p_1-1)?

– YTS

Oct 21 at 0:50

@YTS: oh, sorry. I wrote gcd(…,…)\gcd(\ldots,\ldots) in place of 2gcd(…,…)−12^{\gcd(\ldots,\ldots)}-1. Now fixed.

– Jack D’Aurizio

Oct 21 at 1:17

Why if p2|2gcd(n1,p2−1)−1p_2|2^{gcd(n_1,p_2-1)}-1 and p2≤p1p_2\leq p_1 implies p2p_2.

– YTS

Oct 21 at 1:26

If p2≤p1p_2\leq p_1, p2−1≤p1−1p_2-1\leq p_1-1 splits as a product of primes