Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2002 Indonesia MO Problems/Problem 1"

(Solution to Problem 1)
 
(→‎Problem)
 
(6 intermediate revisions by one other user not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
  
−
Show that <math>n^4 - n^2</math> is divisible by <math>12</math> for any integers <math>n > 1</math>.
+
Show that <math>n^4 - n^2</math> is divisible o by <math>12</math> for any integers <math>n > 1</math>.
  
 
==Solution==
 
==Solution==
  
−
In order for <math>n^4 - n^2</math> to be divisible by <math>12</math>, it must be divisible by <math>4</math> and <math>3</math>.  Note that <math>n^4 - n^2</math> can be factored into <math>n^2 (n+1)(n-1)</math>.
+
In order for <math>n^4 - n^2</math> to be divisible by <math>12</math>, <math>n^4 - n^2</math> must be divisible by <math>4</math> and <math>3</math>.
  
−
If <math>n</math> is even, then <math>n^2 \equiv 0 \pmod{4}</math>.  If <math>n \equiv 1 \pmod{4}</math>, then <math>n-1 \equiv 0 \pmod{4}</math>, and if <math>n \equiv 3 \pmod{4}</math>, then <math>n+1 \equiv 0 \pmod{4}</math>.  That means for all positive <math>n</math>, <math>n^4 - n^2</math> is divisible by <math>4</math>.
+
<br>
 +
'''Lemma 1: <math>n^4 - n^2</math> is divisible by 4'''<br>
 +
Note that <math>n^4 - n^2</math> can be factored into <math>n^2 (n+1)(n-1)</math>.  If <math>n</math> is even, then <math>n^2 \equiv 0 \pmod{4}</math>.  If <math>n \equiv 1 \pmod{4}</math>, then <math>n-1 \equiv 0 \pmod{4}</math>, and if <math>n \equiv 3 \pmod{4}</math>, then <math>n+1 \equiv 0 \pmod{4}</math>.  That means for all positive <math>n</math>, <math>n^2 (n+1)(n-1)</math> is divisible by <math>4</math>.
  
−
If <math>n \equiv 0 \pmod{3}</math>, then <math>n^2 \equiv 0 \pmod{3}</math>.  If <math>n \equiv 1 \pmod{3}</math>, then <math>n-1 \equiv 0 \pmod{3}</math>.  If <math>n \equiv 2 \pmod{3}</math>, then <math>n+1 \equiv 0 \pmod{3}</math>.  That means for all positive <math>n</math>, <math>n^4 - n^2</math> is divisible by <math>3</math>.
+
<br>
 +
'''Lemma 2: <math>n^4 - n^2</math> is divisible by 3'''<br>
 +
Again, note that <math>n^4 - n^2</math> can be factored into <math>n^2 (n+1)(n-1)</math>.  If <math>n \equiv 0 \pmod{3}</math>, then <math>n^2 \equiv 0 \pmod{3}</math>.  If <math>n \equiv 1 \pmod{3}</math>, then <math>n-1 \equiv 0 \pmod{3}</math>.  If <math>n \equiv 2 \pmod{3}</math>, then <math>n+1 \equiv 0 \pmod{3}</math>.  That means for all positive <math>n</math>, <math>n^2 (n+1)(n-1)</math> is divisible by <math>3</math>.
  
−
Because <math>n^4 - n^2</math> is divisible by <math>4</math> and <math>3</math>, it must be divisible by <math>12</math>.
+
<br>
 +
Because <math>n^4 - n^2</math> is divisible by <math>4</math> and <math>3</math>, <math>n^4 - n^2</math> must be divisible by <math>12</math>.
  
 
==See Also==
 
==See Also==
−
{{Indonesia MO 7p box
+
{{Indonesia MO box
 
|year=2002
 
|year=2002
 
|before=First Problem
 
|before=First Problem
 
|num-a=2
 
|num-a=2
 +
|eight=
 
}}
 
}}
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]

Latest revision as of 00:36, 23 November 2021

Problem

Show that $n^4 - n^2$ is divisible o by $12$ for any integers $n > 1$.

Solution

In order for $n^4 - n^2$ to be divisible by $12$, $n^4 - n^2$ must be divisible by $4$ and $3$.


Lemma 1: $n^4 - n^2$ is divisible by 4
Note that $n^4 - n^2$ can be factored into $n^2 (n+1)(n-1)$. If $n$ is even, then $n^2 \equiv 0 \pmod{4}$. If $n \equiv 1 \pmod{4}$, then $n-1 \equiv 0 \pmod{4}$, and if $n \equiv 3 \pmod{4}$, then $n+1 \equiv 0 \pmod{4}$. That means for all positive $n$, $n^2 (n+1)(n-1)$ is divisible by $4$.


Lemma 2: $n^4 - n^2$ is divisible by 3
Again, note that $n^4 - n^2$ can be factored into $n^2 (n+1)(n-1)$. If $n \equiv 0 \pmod{3}$, then $n^2 \equiv 0 \pmod{3}$. If $n \equiv 1 \pmod{3}$, then $n-1 \equiv 0 \pmod{3}$. If $n \equiv 2 \pmod{3}$, then $n+1 \equiv 0 \pmod{3}$. That means for all positive $n$, $n^2 (n+1)(n-1)$ is divisible by $3$.


Because $n^4 - n^2$ is divisible by $4$ and $3$, $n^4 - n^2$ must be divisible by $12$.

See Also

2002 Indonesia MO (Problems)
Preceded by
First Problem 		1 • 2 • 3 • 4 • 5 • 6 • 7 Followed by
Problem 2
All Indonesia MO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_Indonesia_MO_Problems/Problem_1&oldid=165291"