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 "2018 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 2"

m (→‎Solution)
(Included reasoning for solution.)
Line 3: Line 3:
 
Determine all positive integers <math>a</math> such that <math>a < 100</math> and <math>a^3 + 23</math> is divisible by <math>24</math>.
 
Determine all positive integers <math>a</math> such that <math>a < 100</math> and <math>a^3 + 23</math> is divisible by <math>24</math>.
  
−
== Solution==
+
==Solution==
  
 
<math>\{ 1,25,49,73,97 \}</math>
 
<math>\{ 1,25,49,73,97 \}</math>
 +
 +
If <math>{a^3}+23</math> is divisible by <math>24</math>, then so is <math>{a^3}-1</math>. <math>{a^3}-1</math> is the same as <math>(a-1)</math><math>({a^2}+a+1)</math>, and it is divisible by <math>24</math>. There are many options: <math>(a-1)</math> is divisible by <math>24</math>, <math>({a^2}+a+1)</math> is divisible by <math>24</math>, <math>(a-1)</math> is divisible by <math>8</math> and <math>({a^2}+a+1)</math> is divisible by <math>3</math>, and <math>(a-1)</math> is divisible by <math>3</math> and <math>({a^2}+a+1)</math> is divisible by <math>8</math>.
 +
 +
Case 1: <math>(a-1)</math> is divisible by <math>24</math>
 +
 +
This means that <math>a</math> is congruent to <math>1</math> <math>mod</math> <math>(24)</math>. Satisfying the range, the following integers that satisfy are:
 +
 +
{<math>1,25,49,73,97</math>}
 +
 +
Case 2: <math>({a^2}+a+1)</math> is divisible by <math>24</math>
 +
 +
Or <math>a(a+1)</math> is in the form <math>23</math> <math>mod</math> <math>(24)</math>. This means that <math>a(a+1)</math> can be {<math>23,47,71,95</math>}, in the list, the first three numbers are prime, and The fourth can be factorized into two non-consecutive primes. No results from this case.
 +
 +
Case 3: <math>(a-1)</math> is divisible by <math>8</math> and <math>({a^2}+a+1)</math> is divisible by <math>3</math>
 +
 +
<math>a</math> is congruent to <math>1</math> <math>mod</math> <math>(8)</math> or <math>a</math> = <math>8</math> <math>k</math> + <math>1</math> where <math>k</math> is a positive integer. This means that <math>{(8k+1)^2}</math> + <math>8k+1</math> + <math>1</math> = <math>64</math> <math>{k^2}</math> + <math>24</math> <math>k</math> + <math>3</math> which has to be divisible by <math>3</math>. That means so does <math>{k^2}</math>, or <math>k</math> itself is divisible by <math>3</math>. The maximum it can be <math>12</math>, because <math>a<100</math> or <math>a</math> = <math>8k+1</math>. However, for the available values that can be inputted (0,3,6,9,and 12),the same list results from Case 1. No new values.
 +
 +
Case 4: <math>(a-1)</math> is divisible by <math>3</math> and <math>({a^2}+a+1)</math> is divisible by <math>8</math>
 +
 +
<math>a</math> is congruent to <math>1</math> <math>mod</math> <math>(3)</math> or <math>a</math> = <math>3</math> <math>k</math> + <math>1</math> where <math>k</math> is a positive integer. This means that <math>{(3k+1)^2}</math> + <math>3k+1</math> + <math>1</math> = <math>9</math> <math>{k^2}</math> + <math>9</math> <math>k</math> + <math>3</math> which has to be divisible by <math>8</math>. That means so does <math>{k^2}</math> + <math>k</math> + <math>3</math>. Checking k modulo eight for all values might result in a value of k which can narrow down search values.
 +
 +
Sub case 1: k is congruent to -4(mod 8)
 +
 +
<math>{(-4)^2}</math> + <math>-4</math> + <math>3</math> = 7(mod 8)
 +
 +
Sub case 2: k is congruent to -3(mod 8)
 +
 +
<math>{(-3)^2}</math> + <math>-3</math> + <math>3</math> = 1(mod 8)
 +
 +
Sub case 3: k is congruent to -2(mod 8)
 +
 +
<math>{(-2)^2}</math> + <math>-2</math> + <math>3</math> = 5(mod 8)
 +
 +
Sub case 4: k is congruent to -1(mod 8)
 +
 +
<math>{(-1)^2}</math> + <math>-1</math> + <math>3</math> = 3(mod 8)
 +
 +
Sub case 5: k is congruent to  0(mod 8)
 +
 +
<math>{(-0)^2}</math> + <math>-0</math> + <math>3</math> = 3(mod 8)
 +
 +
Sub case 6: k is congruent to  1(mod 8)
 +
 +
<math>{(1)^2}</math> + <math>1</math> + <math>3</math> = 5(mod 8)
 +
 +
Sub case 7: k is congruent to 2(mod 8)
 +
 +
<math>{(2)^2}</math> + <math>2</math> + <math>3</math> = 1(mod 8)
 +
 +
Sub case 8: k is congruent to  3(mod 8)
 +
 +
<math>{(3)^2}</math> + <math>3</math> + <math>3</math> = 7(mod 8)
 +
 +
In no scenario is <math>{k^2}</math> + <math>k</math> + <math>3</math> divisible by <math>8</math>, and by working backward, neither can <math>({a^2}+a+1)</math>. This means that the list noted in Case 1 are all the numbers possible that satisfy the condition. Our answer is <math>\boxed{\textbf{(1,25,49,73,97)}}</math>
  
 
== See also ==
 
== See also ==

Revision as of 17:41, 21 August 2023

Problem

Determine all positive integers $a$ such that $a < 100$ and $a^3 + 23$ is divisible by $24$.

Solution

$\{ 1,25,49,73,97 \}$

If ${a^3}+23$ is divisible by $24$, then so is ${a^3}-1$. ${a^3}-1$ is the same as $(a-1)$$({a^2}+a+1)$, and it is divisible by $24$. There are many options: $(a-1)$ is divisible by $24$, $({a^2}+a+1)$ is divisible by $24$, $(a-1)$ is divisible by $8$ and $({a^2}+a+1)$ is divisible by $3$, and $(a-1)$ is divisible by $3$ and $({a^2}+a+1)$ is divisible by $8$.

Case 1: $(a-1)$ is divisible by $24$

This means that $a$ is congruent to $1$ $mod$ $(24)$. Satisfying the range, the following integers that satisfy are:

{$1,25,49,73,97$}

Case 2: $({a^2}+a+1)$ is divisible by $24$

Or $a(a+1)$ is in the form $23$ $mod$ $(24)$. This means that $a(a+1)$ can be {$23,47,71,95$}, in the list, the first three numbers are prime, and The fourth can be factorized into two non-consecutive primes. No results from this case.

Case 3: $(a-1)$ is divisible by $8$ and $({a^2}+a+1)$ is divisible by $3$

$a$ is congruent to $1$ $mod$ $(8)$ or $a$ = $8$ $k$ + $1$ where $k$ is a positive integer. This means that ${(8k+1)^2}$ + $8k+1$ + $1$ = $64$ ${k^2}$ + $24$ $k$ + $3$ which has to be divisible by $3$. That means so does ${k^2}$, or $k$ itself is divisible by $3$. The maximum it can be $12$, because $a<100$ or $a$ = $8k+1$. However, for the available values that can be inputted (0,3,6,9,and 12),the same list results from Case 1. No new values.

Case 4: $(a-1)$ is divisible by $3$ and $({a^2}+a+1)$ is divisible by $8$

$a$ is congruent to $1$ $mod$ $(3)$ or $a$ = $3$ $k$ + $1$ where $k$ is a positive integer. This means that ${(3k+1)^2}$ + $3k+1$ + $1$ = $9$ ${k^2}$ + $9$ $k$ + $3$ which has to be divisible by $8$. That means so does ${k^2}$ + $k$ + $3$. Checking k modulo eight for all values might result in a value of k which can narrow down search values.

Sub case 1: k is congruent to -4(mod 8)

${(-4)^2}$ + $-4$ + $3$ = 7(mod 8)

Sub case 2: k is congruent to -3(mod 8)

${(-3)^2}$ + $-3$ + $3$ = 1(mod 8)

Sub case 3: k is congruent to -2(mod 8)

${(-2)^2}$ + $-2$ + $3$ = 5(mod 8)

Sub case 4: k is congruent to -1(mod 8)

${(-1)^2}$ + $-1$ + $3$ = 3(mod 8)

Sub case 5: k is congruent to 0(mod 8)

${(-0)^2}$ + $-0$ + $3$ = 3(mod 8)

Sub case 6: k is congruent to 1(mod 8)

${(1)^2}$ + $1$ + $3$ = 5(mod 8)

Sub case 7: k is congruent to 2(mod 8)

${(2)^2}$ + $2$ + $3$ = 1(mod 8)

Sub case 8: k is congruent to 3(mod 8)

${(3)^2}$ + $3$ + $3$ = 7(mod 8)

In no scenario is ${k^2}$ + $k$ + $3$ divisible by $8$, and by working backward, neither can $({a^2}+a+1)$. This means that the list noted in Case 1 are all the numbers possible that satisfy the condition. Our answer is $\boxed{\textbf{(1,25,49,73,97)}}$

See also

2018 UNM-PNM Contest II (Problems • Answer Key • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10
All UNM-PNM Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_UNM-PNM_Statewide_High_School_Mathematics_Contest_II_Problems/Problem_2&oldid=197281"