ISI Problem 7 2018

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

ISI Problem 7 2018

G H J

Reveal topic tags

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.

27 posts

rayuga

#1 h May 13, 2018, 11:06 AM • 3 Y

Y by Adventure10, Mango247, cubres

Let $a, b, c$ are natural numbers such that $a^{2}+b^{2}=c^{2}$ and $c-b=1$
Prove that

$(i)$ $a$ is odd.
$(ii)$ $b$ is divisible by $4$
$(iii)$ $a^{b}+b^{a}$ is divisible by $c$

This post has been edited 1 time. Last edited by rayuga, May 13, 2018, 11:07 AM
Reason: Latex

Z K Y

The post below has been deleted. Click to close.

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

643 posts

#2 h May 13, 2018, 11:25 AM • 8 Y

Y by Wizard_32, integrated_JRC, AlastorMoody, Pluto1708, Euler01, Adventure10, Mango247, cubres

(i) $a^2+b^2=c^2\implies a^2=(b+1)^2-b^2\implies a^2=2b+1.$
(ii) $b=\frac{(a-1)(a+1)}2,$ since $a$ is odd, so $8\mid (a-1)(a+1).$
(iii) $c\mid a^b+b^a\iff b+1 | a^b+b^a \iff b+1 | a^b-1\iff b+1 | (2b+1)^{\tfrac{b}{2}}-1\iff b+1 | (-1)^{\tfrac{b}{2}}-1\iff b+1 | 0$ since $4|b$

This post has been edited 5 times. Last edited by ayan.nmath, May 13, 2018, 11:27 AM

Z K Y

The post below has been deleted. Click to close.

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

2130 posts

Sayan

#3 h May 13, 2018, 11:26 AM • 4 Y

Y by ring_r, Adventure10, Mango247, cubres

i) $a^2=c^2-b^2=(b+1)^2-b^2=2b+1$ which is odd

ii) $a$ must be of the form $4k+1$ or $4k-1$
Then $2b=a^2-1=16k^2 \pm 8k$ which is divisible by $8$ . Hence by is divisible by $4$ .

iii) $a$ is odd. Hence $c=b+1$ divides $b^a+1$ . $b$ is divisible by $4$ . Hence $a^4-1$ divides $a^b-1$ . But $a^4-1$ contains a factor $a^2+1=2c$ . Hence $c$ divides $a^b-1$ . Combining the two, we get the result.

Z K Y

The post below has been deleted. Click to close.

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

27 posts

rayuga

#4 h May 13, 2018, 11:43 AM • 3 Y

Y by Adventure10, Mango247, cubres

My solution is same as comment 2.
(I use modulo's along with proofs)

This post has been edited 2 times. Last edited by rayuga, May 13, 2018, 2:34 PM
Reason: Latex

Z K Y

The post below has been deleted. Click to close.

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

56 posts

#5 h May 14, 2018, 2:01 PM • 3 Y

Y by Adventure10, Mango247, cubres

Part a) c is even b is odd so a is odd
c is odd b is even so a is odd
b) a^2-1/2=b
Hence if a is odd then a=2k+1 hence 2/k*(k+1) so 4 /b
c) same as in post 1

This post has been edited 1 time. Last edited by Spideymath, May 14, 2018, 2:03 PM

Z K Y

The post below has been deleted. Click to close.

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

6107 posts

#6 h Aug 30, 2019, 4:15 PM • 2 Y

Y by Adventure10, cubres

Could someone explain in detail the third part? I couldn't get the jump at step 3 in first solution.

Z K Y

The post below has been deleted. Click to close.

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

820 posts

#7 h Aug 30, 2019, 5:51 PM • 2 Y

Y by Adventure10, cubres

Relatively simple problem, especially with a little background in number theory...

Part $a$ is quite trivial- we get $a^2+b^2=(b+1)^2=>a^2=2b+1=> a \equiv 1 \pmod{2}$ , hence done.

$b$ is almost as easy- noticing that $8 \mid a^2-1$ for odd $a$ $=> 8 \mid 2b => 4 \mid b$ .

$c$ would've been, I think, significantly tougher without $a$ and $b$ , but anyways let's work backwards-
We need to prove $a^b +b^a \equiv 0 \pmod{c} <=> a^b+(c-1)^a \equiv 0 <=> a^b \equiv 1 \pmod c$ (as $a$ is odd $=>-1^a \equiv -1 \pmod{c}$ ).

Ok so now let's wrap up the problem using our previously derived equation:
$a^2=2b+1 => a^2=2c-1 => a^2 \equiv -1 \pmod{c} => a^4 \equiv 1 \pmod{c}$ . But, as $4 \mid b$ , we're done (formally, I'd write that as $4=O_c(a) \mid b => a^b \equiv 1 \pmod{c}$ , but that's just the same thing).

This post has been edited 1 time. Last edited by ubermensch, Aug 30, 2019, 5:52 PM

Z K Y

The post below has been deleted. Click to close.

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

651 posts

#8 h Mar 21, 2020, 8:28 PM • 6 Y

Y by Gerninza, rounak138, Mango247, Mango247, Mango247, cubres

$\textbf{Part (i)}$ .

We are given that $c-b=1$ .

$\implies c^2-b^2=c+b$ , $\implies a^2=b+c$ .

$a^4=(b+c)^2=(b-c)^2+4bc=4bc +1$ .

$\implies a\equiv \text{odd}$

$\textbf{part(ii)}$ .

WLOG $c=s^2+t^2,b=2st$ . $\implies a=s^2-t^2$ .

Where $s>t ,s,t\in \mathbb{N}$ .

Since $c-b=1$ , $\implies (s-t)^2=1$ .

$\implies s-t=1$ .

So $s$ and $t$ has opposite pairty .

$\implies St\equiv \text{even}$ .

$\implies 4\mid b$

$\textbf{part(III)}$ .

See $s^2+t^2 -2st \equiv 1\pmod{s^2+t^2}$ .

$\implies 2st \equiv (-1) \pmod{s^2+t^2}$ .

Note , $(s+t)^{2st}=(s^2+t^2+2st)^{st} \equiv 1\pmod{s^2+t^2}$ .[since $st$ even]

again we get $s+t$ is odd so , $(2st)^{s+t} \equiv -1 \pmod{s^2+t^2}$ .

So $c\mid a^b +b^a$ .

This post has been edited 1 time. Last edited by ftheftics, Mar 21, 2020, 8:32 PM
Reason: Hh

Z K Y

The post below has been deleted. Click to close.

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

531 posts

#9 h Mar 22, 2020, 7:02 AM • 1 Y

Y by cubres

rayuga wrote:

Let $a, b, c$ are natural numbers such that $a^{2}+b^{2}=c^{2}$ and $c-b=1$
Prove that

$(i)$ $a$ is odd.
$(ii)$ $b$ is divisible by $4$
$(iii)$ $a^{b}+b^{a}$ is divisible by $c$

1) Same as #2 ie $a^2=2b+1$

2) Assume to the contrary that $4\nmid b$
Therefore only possible cofiguration : $b^2\equiv 1\pmod{4}$ and $a^2\equiv 0\pmod{4}$ and $c^2\equiv 1\pmod{4}$
But this is not possible because $a^2=2b+1$

3) $a^2=2b+1$ and $c=b+1$
$\implies a^2\equiv b\equiv -1\pmod{c}$
$\implies a^b+b^a\equiv a^{2\cdot \frac{b}{2}}+(-1)^a\equiv (-1)^{\frac{b}{2}}+(-1)^a\pmod{c}$
Now $a$ is odd and $\frac{b}{2}$ is even.
$\implies (-1)^{\frac{b}{2}}+(-1)^a\equiv 1-1\equiv 0\pmod{c}$

This post has been edited 1 time. Last edited by Bumblebee60, Mar 22, 2020, 7:04 AM

Z K Y

The post below has been deleted. Click to close.

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

390 posts

#10 h Mar 22, 2020, 4:25 PM • 2 Y

Y by abhisruta03, cubres

rayuga wrote:

Let $a, b, c$ are natural numbers such that $a^{2}+b^{2}=c^{2}$ and $c-b=1$
Prove that

$(i)$ $a$ is odd.
$(ii)$ $b$ is divisible by $4$
$(iii)$ $a^{b}+b^{a}$ is divisible by $c$

$a, b, c$ are pythagoran triplet now as for every pythagoran triplet there always exist integer $m, n$ such that $a=m^2-n^2$ , $b=2*m*n$ , $c=m^2+n^2$
Then as $c-b=1$ $\implies (m-n)^2 =1$ hence $m=1+n$ now for

$(i)$
as $a=(1+n)^2 - n^2$ $\implies 1+2n=a$ hence clearly $a=odd$

$(ii)$
as $b=2*m*n=2(1+n)*n$ hence $b=4k$

$(iii)$
as $b=2n+2n^2=c-1$ , $a^2=2c-1$
$a^b +b^a=(2c-1)^{2k}+(c-1)^a$ here $b=4k$
Now as $(2c-1)^{2k} +(c-1)^a \equiv (-1)^{2k} +(-1)^a \equiv 0 mod(c)$

This post has been edited 3 times. Last edited by Maths_1729, Mar 22, 2020, 7:24 PM
Reason: \implies

Z K Y

The post below has been deleted. Click to close.

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

20 posts

#11 h Apr 14, 2025, 4:33 PM • 1 Y

Y by cubres

part1: $a^2=c^2-b^2=c-b \equiv 1 (mod 2)$
Part2: $a^2+b^2=(b+1)^2=b^2+2b+1\implies2b=a^2-1 \equiv 0 (mod 8)$ since a is odd. so $4\mid b$
part3: $b\equiv-1(mod c) \implies b^a \equiv (-1)^a \equiv -1 (mod c)$ (since a is odd)
assume $b=4k$ so, $a^2 \equiv c+b \equiv -1 (mod c) \implies a^{4k}=a^b \equiv (-1)^{2k} \equiv 1 (mod c)$
hence, $c \mid a^b+b^a$ $\blacksquare$

This post has been edited 1 time. Last edited by Mathworld314, Apr 15, 2025, 4:20 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a