3^n-2^n

R. Gerbicz · 2007-04-08, 23:17

Prove that: if n>1 is an integer, then $3^n-2^n$ isn't divisible by n.

nibble4bits · 2007-05-14, 22:03

Easy, if you assume this is true:
0 != 1

Hint: Use the property of "a^b mod c" that it maps to "(a mod c)^(b mod c-1)" to start.

nibble4bits · 2007-05-15, 05:38

My strategy for this problem is to (try to) find a case where $(3^n - 2^n) \bmod n = 0$ , and the way I attempt this is to find a simpler equation that is equal to zero if and only if the original equation equals zero.

The obvious one of course is the one that (ab?)uses modular math, in order to get my answer $1 \neq 0$ .

The interesting question is of course, that if instead of 3 and 2 and 1, we had a and b and c, would we always get $a-b = c \bmod n$ as our solution? I haven't figured that one out but I think it can't be that hard to find out.

There's another part that I wrote down that was important... I'll have to type it up lator. Don't worry, since this covers most of the problem. :)

axn · 2007-05-15, 06:28

Quote:

Originally Posted by nibble4bits

Hint: Use the property of "a^b mod c" that it maps to "(a mod c)^(b mod c-1)" to start.

True for prime c. In general, not true for composite c.

Citrix · 2007-05-16, 09:00

I'll just give a hint here:

3^n-2^n==0 (mod n) is the same as (3/2)^n-1==0 (mod n)

Since 3/2 does not have an integer solution for even n, even n can be excluded. Multiples of 3 can also be excluded.

Prime n can also be excluded by fermat's little theorem.

THink about a^n-1==0 (mod n).

alpertron · 2007-05-16, 12:16

Quote:

Originally Posted by Citrix

I'll just give a hint here:

3^n-2^n==0 (mod n) is the same as (3/2)^n-1==0 (mod n)

Since 3/2 does not have an integer solution for even n, even n can be excluded. Multiples of 3 can also be excluded.

When n is even, 3^n-2^n==0 (mod n) does not imply that (3/2)^n-1==0 (mod n).

In this case it should be both 3^n-2^n==0 (mod 2) and 3^n-2^n==0 (mod n/2). But since 3^n is odd and 2^n is even, the first congruence is false so the original congruence does not hold modulo even n.

Suppose now that n=pq where both p and q are prime numbers different from 2 and 3 (because those cases were already solved).

Now we have (3/2)^(pq) - 1 == 0 (mod pq)

Using modulo p: (3/2)^q - 1 == 0 (mod p) (1)
Using modulo q: (3/2)^p - 1 == 0 (mod q) (2)

From (1) we get that gcd(q, p-1) > 1, but since q is prime we get that q is a divisor of p-1, so q < p.

From (2) we get that gcd(p, q-1) > 1, but since p is prime we get that p is a divisor of q-1, so p < q.

So this contradiction means that n=pq (both factor primes) cannot be used for 3^n-2^n==0 (mod n).

alpertron · 2007-05-16, 13:07

The previous method can be extended for all n:

Let $n = p_1*p_2*...*p_k$ where all p are primes.

So we have:

$\left(\frac{3}{2}\right)^{p_1*p_2*...*p_k} - 1\equiv 0\pmod{p_1*p_2*...*p_k}$

Operating modulo $p_i$ we get k congruences of the form:

$\left(\frac{3}{2}\right)^{p_1*p_2*...*p_k/p_i} - 1\equiv 0\pmod {p_i}$

Since $\gcd(p_1*p_2*...*p_k/p_i, p_i-1) > 1$ , $p_i-1$ is a multiple of at least one of the other primes, so we get that $p_i$ is greater than some of the other primes.

We can build a chain ordering the primes from greatest to lowest, but we will have a problem with the last prime, because it is greater than one that is already listed on the chain. This contradiction means that no value of n can be used for the original congruence.

masser · 2007-05-16, 21:04

3^n - 2^n is always odd, so it's impossible for even n to divide 3^n - 2^n.

For n odd, use the binomial theorem:

1 = (3-2)^n = 3^n - 2^n + intermediate terms

=> 3^n - 2^n = 1 - intermediate terms.

I'm feeling lazy and don't want to do the necessary typesetting, but you can show that the intermediate terms are divisible by n. Hence, 3^n - 2^n is not divisible by n.

maxal · 2007-05-17, 00:48

Assume that a set $M=\{ n>1\ :\ n|(3^n-2^n)\}$ is not empty. As it was already noticed, all elements of M are odd.

Consider a set $P=\{ p\ \mbox{prime}\ :\ \exists n\in M,\ p|n\}$ of primes dividing elements of M.
Note that if prime p belongs to P, then the prime divisors (each of which is strictly smaller than p) of the multiplicative order of 3/2 modulo p also belong to P.

Let q be the smallest element of P (note that q must be an odd prime). Then the multiplicative order of 3/2 modulo q is 1, that is not possible. Contradiction proves that the set M is empty.

alpertron · 2007-05-17, 02:44

Quote:

Originally Posted by masser

3^n - 2^n is always odd, so it's impossible for even n to divide 3^n - 2^n.

For n odd, use the binomial theorem:

1 = (3-2)^n = 3^n - 2^n + intermediate terms

=> 3^n - 2^n = 1 - intermediate terms.

I'm feeling lazy and don't want to do the necessary typesetting, but you can show that the intermediate terms are divisible by n. Hence, 3^n - 2^n is not divisible by n.

This works when n is prime. But when n=35, for example, we get (3^35-2^35)=29 (mod 35), not 1.

2007-04-08, 23:17	#1
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 5CE₁₆ Posts	3^n-2^n Prove that: if n>1 is an integer, then $3^n-2^n$ isn't divisible by n.

2007-05-15, 05:38	#3
nibble4bits Nov 2005 2·7·13 Posts	My strategy for this problem is to (try to) find a case where $(3^n - 2^n) \bmod n = 0$ , and the way I attempt this is to find a simpler equation that is equal to zero if and only if the original equation equals zero. The obvious one of course is the one that (ab?)uses modular math, in order to get my answer $1 \neq 0$ . The interesting question is of course, that if instead of 3 and 2 and 1, we had a and b and c, would we always get $a-b = c \bmod n$ as our solution? I haven't figured that one out but I think it can't be that hard to find out. There's another part that I wrote down that was important... I'll have to type it up lator. Don't worry, since this covers most of the problem. :) Last fiddled with by nibble4bits on 2007-05-15 at 05:41

2007-05-16, 09:00	#5
Citrix Jun 2003 2×7×113 Posts	I'll just give a hint here: 3^n-2^n==0 (mod n) is the same as (3/2)^n-1==0 (mod n) Since 3/2 does not have an integer solution for even n, even n can be excluded. Multiples of 3 can also be excluded. Prime n can also be excluded by fermat's little theorem. THink about a^n-1==0 (mod n). Last fiddled with by Citrix on 2007-05-16 at 09:02

2007-05-16, 13:07	#7
alpertron Aug 2002 Buenos Aires, Argentina 2×683 Posts	The previous method can be extended for all n: Let $n = p_1p_2...p_k$ where all p are primes. So we have: $\left(\frac{3}{2}\right)^{p_1p_2...p_k} - 1\equiv 0\pmod{p_1p_2...p_k}$ Operating modulo $p_i$ we get k congruences of the form: $\left(\frac{3}{2}\right)^{p_1p_2...p_k/p_i} - 1\equiv 0\pmod {p_i}$ Since $\gcd(p_1p_2...p_k/p_i, p_i-1) > 1$ , $p_i-1$ is a multiple of at least one of the other primes, so we get that $p_i$ is greater than some of the other primes. We can build a chain ordering the primes from greatest to lowest, but we will have a problem with the last prime, because it is greater than one that is already listed on the chain. This contradiction means that no value of n can be used for the original congruence. Last fiddled with by alpertron on 2007-05-16 at 13:20*

2007-05-17, 00:48	#9
maxal Feb 2005 2²·3²·7 Posts	Assume that a set $M=\{ n>1\ :\ n\|(3^n-2^n)\}$ is not empty. As it was already noticed, all elements of M are odd. Consider a set $P=\{ p\ \mbox{prime}\ :\ \exists n\in M,\ p\|n\}$ of primes dividing elements of M. Note that if prime p belongs to P, then the prime divisors (each of which is strictly smaller than p) of the multiplicative order of 3/2 modulo p also belong to P. Let q be the smallest element of P (note that q must be an odd prime). Then the multiplicative order of 3/2 modulo q is 1, that is not possible. Contradiction proves that the set M is empty. Last fiddled with by maxal on 2007-05-17 at 00:53

2007-05-14, 22:03	#2
nibble4bits Nov 2005 2×7×13 Posts	Easy, if you assume this is true: 0 != 1 Hint: Use the property of "a^b mod c" that it maps to "(a mod c)^(b mod c-1)" to start.

2007-05-16, 21:04	#8
masser Jul 2003 wear a mask 2²·419 Posts	3^n - 2^n is always odd, so it's impossible for even n to divide 3^n - 2^n. For n odd, use the binomial theorem: 1 = (3-2)^n = 3^n - 2^n + intermediate terms => 3^n - 2^n = 1 - intermediate terms. I'm feeling lazy and don't want to do the necessary typesetting, but you can show that the intermediate terms are divisible by n. Hence, 3^n - 2^n is not divisible by n.