Divisible by 6 & 7 not both

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

Divisible by 6 & 7 not both

G H J

Reveal topic tags

contest problem

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

Source: Bangladesh National Mathematical Olympiad 2016

The post below has been deleted. Click to close.

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

Olympus_mountaineer

414 posts

Olympus_mountaineer

#1 h Feb 26, 2019, 6:16 PM • 2 Y

Y by Adventure10, Mango247

(a) Show that $n(n + 1)(n + 2)$ is divisible by $6$ .

(b) Show that $1^{2015} + 2^{2015} + 3^{2015} + 4^{2015} + 5^{2015} + 6^{2015}$ is divisible by $7$ .

This post has been edited 1 time. Last edited by Amir Hossein, Jan 15, 2025, 2:45 AM

Z K Y

The post below has been deleted. Click to close.

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

820 posts

#2 h Feb 26, 2019, 6:44 PM • 3 Y

Y by Vndom, Adventure10, Mango247

(a) 3 consecutive integers are divisible by 2,3.
(b) $1^{2015}+6^{2015}=1^{2015}-1^{2015}=0(mod 7)$ . Similarly for $(2,5),(3,4)=(2,-2),(3,-3)(mod7)$
Q.E.D.

Z K Y

The post below has been deleted. Click to close.

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

Olympus_mountaineer

414 posts

Olympus_mountaineer

#3 h Feb 26, 2019, 7:00 PM • 2 Y

Y by Adventure10, Mango247

(a)

$(n-1)\times n\times(n+1)=(n^2-n)(n+1)$ [According to fermat's little theorem given expression is divided by $2$ ]

$(n-1)\times n\times (n+1)=(n^2-n)(n+1)=n^3-n$ [According to fermat's little theorem given expression is divided by $3$ ]

So, $(n-1)\times n\times (n+1)$ is divided by $2\times 3$ or $6$ . Proved.

Z K Y

The post below has been deleted. Click to close.

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

Aimingformygoal

126 posts

Aimingformygoal

#4 h May 19, 2020, 4:23 PM

Y by

Click to reveal hidden text

This post has been edited 3 times. Last edited by Aimingformygoal, May 19, 2020, 4:25 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

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

744 posts

#5 h May 19, 2020, 4:45 PM

Y by

Solution

This post has been edited 1 time. Last edited by Hamroldt, May 19, 2020, 4:46 PM
Reason: Latex Error

Z K Y

The post below has been deleted. Click to close.

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

562 posts

Dr_Vex

#6 h Jun 1, 2020, 11:40 AM • 1 Y

Y by Purple_Planet

Do these types of problem really appear in NMO?

This post has been edited 1 time. Last edited by Dr_Vex, Jun 1, 2020, 11:40 AM

Z K Y

The post below has been deleted. Click to close.

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

351 posts

Vndom

#7 h Jun 1, 2020, 12:20 PM • 3 Y

Y by Mango247, Mango247, Mango247

We can also use induction for the first question.

Z K Y

The post below has been deleted. Click to close.

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

488 posts

#8 h Jun 1, 2020, 1:12 PM

Y by

a)
We know that every second integer is divisible by 2, and every third is divisible by 3, so there is at least one factor of 2 and 3, so we are done.

Z K Y

The post below has been deleted. Click to close.

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

351 posts

Vndom

#9 h Jun 1, 2020, 1:56 PM

Y by

Show that $n(n + 1)(n + 2)$ is divisible by $6$ . (I'm assuming for positive numbers, can be extended similarly to negative numbers and so on)
$\text{Proof:}$
$\textbf{Base Case:}$ let the least number, $n$ , be $1$
then, we have $n(n+1)(n+2)=1(2)(3)$ , which is clearly divisible by $3$

$\textbf{Inductive Step:}$ assume this is true for some $n=k, k\in\mathbb{Z^+}$
we have $k(k+1)(k+2)=3m, m\in\mathbb{Z^+}$

$\textbf{Proof for } n=k+1\textbf{:}$ if our argument is to hold true, then $(k+1)(k+2)(k+3)=3p, p\in\mathbb{Z^+}$
simplifying the $\textbf{LHS},$ we see it is equal to
$k^3+3k^2+3k^2+9k+2k+6$ but we also know that $k(k+1)(k+2)=3m=k^3+3k^2+2k$ ; substituting this in,
we see $k^3+3k^2+3k^2+9k+2k+6=3m+3k^2+9k+6=3m+3(k^2+9k+6)$ now since, $k\in\mathbb{Z^+},$ we know that $k^2+9k+6$ is divisible by $3,$ meaning $3|$ $k^3+3k^2+3k^2+9k+2k+6\Rightarrow3|(k+1)(k+2)(k+3)$ and satisfying $p\in\mathbb{Z^+}.$
By the $\textbf{PMI}$ , this result holds true for all positive $n.$ Similar arguments can be made to extend this argument to other sets of numbers.

This post has been edited 8 times. Last edited by Vndom, Jun 1, 2020, 2:05 PM

Z K Y

The post below has been deleted. Click to close.

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

2502 posts

ATGY

#10 h Oct 25, 2020, 7:30 AM

Y by

Prabh1512 wrote:

Solution

If I'm not wrong isn't this circular logic... ?? Or does such a theorem exist already because I don't know about it

(a) By definition, there is a multiple of 3 every three consecutive numbers, there is a multiple of 2 every two consecutive numbers. Since $n(n + 1)(n + 2)$ is a set of three consecutive numbers. Thus there would be one multiple of 3 and 1 or 2 multiples of 2, so it would divide 6 (as $3\cdot 2 = 6$ ).

(b) Notice that $1^{2015} + 6^{2015} \equiv 0\pmod7$ (using pattern bash), as well as $2^{2015} + 5^{2015} \equiv 0\pmod7$ , $3^{2015} + 4^{2015} \equiv 0\pmod7$ , thus the sum would be divisble by $7$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

429 posts

R-sk

#11 h Jan 10, 2021, 2:23 PM

Y by

For first it is direct induction and for second we can use the identity that if n is odd then $a^n+b^n$ =(a+b) ( $a^{n-1}....... b^{n-1}$ ) then proof of second is done

Z K Y

The post below has been deleted. Click to close.

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

5538 posts

#12 h Nov 13, 2021, 3:38 PM

Y by

We assume $n$ is a positive integer.

Part (a)

Part (b)

This post has been edited 1 time. Last edited by megarnie, Nov 13, 2021, 3:38 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a