A 18

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

w

1 user

TOPICS

No tags match your search

M

No tags match your search

M

A 18

G H J

Reveal topic tags

difference of squares

special factorizations

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

Let $m$ and $n$ be natural numbers and let $mn+1$ be divisible by $24$ . Show that $m+n$ is divisible by $24$ .

Z K Y

The post below has been deleted. Click to close.

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

315 posts

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

Y by Wizard_32, Adventure10, and 1 other user

Seems a little straightforward.

In $\mathbb{Z}_8$ , $mn=-1$ has solutions $\{m,n\}=\{1,7\},\{3,5\}$ and in both cases $m+n=0$ .
In $\mathbb{Z}_3$ , $mn=-1$ has solution $\{m,n\}=\{1,2\}$ and again $m+n=0$ , so $24|m+n$ .

Z K Y

The post below has been deleted. Click to close.

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

145 posts

#3 h Jul 17, 2008, 12:44 PM • 1 Y

Y by Adventure10

Let

$m = 24k_1 + r_1$ and
$n = 24k_2 + r_2$

$0 \le r_1,r_2 <24$

Since $24|mn + 1 \rightarrow mn \equiv r_1r_2 \equiv 23$ ( mod $24$ ).

Since $23$ is prime and $r_1$ and $r_2$ are integers then $r_1 = 1$ and $r_2 = 23$ (or $r_1 = 23$ and $r_2 = 1$ ).

So $m + n = 24k_1 + r_1 + 24k_2 + r_2 = 24(k_1 + k_2) + 1 + 23 = 24(k_1 + k_2 + 1)$

Quote:

Seems a little straightforward.

yeah it is

Z K Y

The post below has been deleted. Click to close.

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

352 posts

ali666

#4 h Jul 17, 2008, 8:47 PM • 2 Y

Y by Adventure10, Mango247

Wichking wrote:

Since $23$ is prime and $r_1$ and $r_2$ are integers then $r_1 = 1$ and $r_2 = 23$ (or $r_1 = 23$ and $r_2 = 1$ ).

you are wrong...if $r_1=7 , r_2=17$ then $r_1r_2\equiv23 (\mod 24)$

Z K Y

The post below has been deleted. Click to close.

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

145 posts

#5 h Jul 18, 2008, 4:17 PM • 1 Y

Y by Adventure10

you are correct

in fact

there are 4 such pairs

$(1,23)$
$(5,19)$
$(7,17)$
$(11,13)$

(we can show that these are the only such pairs and their sum is always 24)... but that makes my solution even more ugly

Z K Y

The post below has been deleted. Click to close.

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

14 posts

#6 h Apr 18, 2013, 2:40 PM • 2 Y

Y by Adventure10, Mango247

$24$ divides $mn+1$ and we see $m,n$ are both odd numbers of the form $2k_1 +1,2k_2+1$ .
We observe $m+n+mn+1 =(m+1)(n+1)$
=> $(2k_1+2)(2k_2+2) =4(k_1+1)(k_2+1)$
If $24$ divides $4(k_1+1)(k_2+1)$ then $6$ divides $(k_1+1)(k_2+1)$ ........( $1$ )
=> $2$ divides $(k_1+1)$ or $(k_2+1)$ or both……..( $2$ )
$24$ divides $(4k_1k_2+2(k_1+k_2)+2)$ which means $12$ divides $(2k_1k_2+k_1+k_2+1)$
 $2$ divides $k_1+k_2+1$ so $k_1,k_2$ cannot both be odd or even. Either of them would be odd.
Therefore $2$ divides $k_1+1$ or $k_2+1$ proving ( $2$ ).
$3$ divides $2k_1k_2+k_1+k_2+1$  $3$ divides $-k_1k_2+k_1+k_2+1=-k_1(k_2-1) +k_2+1$
If $3$ does not divide $k_2$ then $3$ divides $k_2-1$ or $k_2+1$ . If $3$ divides $k_2-1$ then
$3$ divides $k_2+1$ a contradiction. Therefore $3$ divides $k_2+1$ . If $3$ divides $k_2$ then $3$
Divides $k_1+1$ .
$2$ divides $k_1+1$ or $k_2+1$ and $3$ divides $k_1+1$ or $k_2+1$  $6$ divides $(k_1+1)(k_2+1)$
Thus proving ( $1$ )

Z K Y

The post below has been deleted. Click to close.

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

688 posts

#7 h Oct 1, 2013, 6:05 AM • 2 Y

Y by Adventure10, Mango247

A related problem:
If $mn+1$ is divided by k,then $m+n$ is divided by k.
Find the maximimu of $k$ .( $k_{max}=24$ )

Z K Y

The post below has been deleted. Click to close.

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

6012 posts

MSTang

#8 h Jan 1, 2015, 11:09 PM • 4 Y

Y by jam10307, Wizard_32, Adventure10, Mango247

My solution: here

Z K Y

The post below has been deleted. Click to close.

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

1791 posts

#9 h Jan 2, 2015, 9:32 PM • 2 Y

Y by Adventure10, Mango247

Z K Y

The post below has been deleted. Click to close.

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

548 posts

#12 h Dec 18, 2021, 5:27 PM

Y by

mod3, mod8

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

#13 h Sep 19, 2024, 4:09 PM

Y by

Since mod $3$ is easy I'll only check mod $8$ . Note that $\gcd(2,mn)=1$ , so we can write $n\equiv -\frac 1m \pmod 8$ . We need to prove $m-\frac 1m\equiv 0 \pmod 8$ , which is obvious by casework.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a