A 41

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 41

G H J

Reveal topic tags

modular arithmetic

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 Davi-8191, Adventure10, Mango247

Show that there are infinitely many composite numbers $n$ such that $3^{n-1}-2^{n-1}$ is divisible by $n$ .

Z K Y

The post below has been deleted. Click to close.

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

1144 posts

Tiks

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

Y by JasperL, Wizard_32, Adventure10, Mango247

Peter wrote:

Show that there are infinitely many composite numbers $n$ such that $3^{n-1}-2^{n-1}$ is divisible by $n$ .

We prove that for any positive integer $m$ the number $n=3^{2^{m}}-2^{2^{m}}$ satisfies the problems condition. Indeed, we have that if $a|b$ then $3^{a}-2^{a}|3^{b}-2^{b}$ so to prove that $n|3^{n-1}-2^{n-1}$ it is sufficent to prove that $2^{m}|n-1$ ,that is $2^{m}|(3^{2^{m}}-1)-2^{2^{m}}$ . Since $2^{m}\geq m$ , then $2^{m}|2^{2^{m}}$ and we only need to verify that $2^{m}|3^{2^{m}}-1$ . It is easy to see that $3^{2^{m}}-1=(3-1)(3+1)(3^{2}+1)...(3^{2^{m-1}}+1)$ which shows that $3^{2^{m}}-1$ is a product of $8=(3-1)(3+1)$ and $m-1$ even numbers and thus is divisible by $2^{m}$ (actually we have proved that it is divisible by $2^{m+2}$ ).

Z K Y

The post below has been deleted. Click to close.

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

5 posts

#3 h Feb 21, 2014, 3:31 PM • 3 Y

Y by ali.agh, Adventure10, Mango247

I will post bellow a solution for a generalization of this problem.

Let $a$ and $b$ be positive integers such that $a>b$ and they are coprime.
Show that there are infinitely many composite numbers $n$ such that
$a^{n-1}-b^{n-1}$ is divisible by $n$ .

Solution:
We take an arbitrary prime number $p$ such that $a^2-b^2$ isn't divisible by $p$ .
We will show that the number $n = \frac{a^{2p}-b^{2p}}{a^2-b^2}$ satisfies the problem's condition.

$n = \frac{a^{2p}-b^{2p}}{a^2-b^2} = \frac{a^{p}-b^{p}}{a-b}\cdot\frac{a^{p}+b^{p}}{a+b}\newline = (a^{p-1}+a^{p-2}b+\cdots+b^{p-1})(a^{p-1}-a^{p-2}b+\cdots+b^{p-1})$ .
Obviously,we have
$a^{p-1}+a^{p-2}b+\cdots+b^{p-1}>a^{p-1}-a^{p-2}b+\cdots+b^{p-1}>1$ .
Therefore $n$ is a composite number.

$(a^2-b^2)n \equiv a^{2p}-b^{2p} \equiv a^2-b^2 \pmod{p}$ .
Since $a^2-b^2$ and $p$ are coprime, we have $n \equiv 1 \pmod{p}$ .
I claim that $n$ is an odd number. Otherwise, $n$ is an even number.
The equation $(a^2-b^2)n = a^{2p}-b^{2p}$ implies that $a^{2p}-b^{2p}$ is an even number.
So we have that $a$ and $b$ have same parity.
Since they are coprime, they are odd numbers.
But we have $n \equiv a^{2p-2}+a^{2p-4}b^2+\cdots+b^{2p} \equiv 1+1+\cdots+1 \equiv p \equiv 1 \pmod{2}$ .
This is a contradiction.

From the above, $n-1$ is divisible by $2p$ .
Or there is a positive integer $k$ such that $n-1=2pk$ .
The equation $(a^2-b^2)n = a^{2p}-b^{2p}$ implies that $a^{2p} \equiv b^{2p} \pmod{n}$ .
Therefore, we have $a^{n-1} \equiv a^{2pk} \equiv b^{2pk} \equiv b^{n-1} \pmod{n}$ .

So,we have done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a