3^n-2^n
 

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

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

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

My strategy for this problem is to (try to) find a case where [tex] (3^n - 2^n) \bmod n = 0 [/tex], 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 [tex]1 \neq 0[/tex].

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 [tex] a-b = c \bmod n[/tex] 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. :)

[QUOTE=nibble4bits;106073]Hint: Use the property of "a^b mod c" that it maps to "(a mod c)^(b mod c-1)" to start.[/QUOTE]

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

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).

[QUOTE=Citrix;106219]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.
[/QUOTE]
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).

The previous method can be extended for all n:

Let [tex]n = p_1*p_2*...*p_k[/tex] where all p are primes.

So we have:

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

Operating modulo [tex]p_i[/tex] we get k congruences of the form:

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

Since [tex]\gcd(p_1*p_2*...*p_k/p_i, p_i-1) > 1[/tex], [tex]p_i-1[/tex] is a multiple of at least one of the other primes, so we get that [tex]p_i[/tex] 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.

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.

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

Consider a set [tex]P=\{ p\ \mbox{prime}\ :\ \exists n\in M,\ p|n\}[/tex] 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.

[QUOTE=masser;106270]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.[/QUOTE]
This works when n is prime. But when n=35, for example, we get (3^35-2^35)=29 (mod 35), not 1.