Do not try to case bash lol

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

Do not try to case bash lol

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Own , Mock Thailand Mathematic Olympiad P3

The post below has been deleted. Click to close.

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

149 posts

#1 h Apr 30, 2025, 9:08 AM

Y by

Let $n,d\geqslant 6$ be a positive integer such that $d\mid 6^{n!}+1$ .
Prove that $d>2n+6$ .

Z K Y

The post below has been deleted. Click to close.

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

77 posts

Haris1

#2 h Apr 30, 2025, 9:36 AM • 2 Y

Y by ItzsleepyXD, Rayanelba

We get $2^{v_{2}(n!)+1}|\phi(d)$ ,
bounding it we get $d>\phi(d)\geq2^{v_{2}(n!)+1}$ , it is easy to show that the expression with power of $2$ is bigger than $2n+6$ for $n\geq6$

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

642 posts

cursed_tangent1434

#3 h May 1, 2025, 5:54 AM • 2 Y

Y by ehuseyinyigit, reni_wee

Extremely trivial. Same essential idea as the above post but with more details.

Note that if $p \mid d$ is a prime, then clearly $p \not \in \{2,3\}$ since the left hand side is relatively prime to $6$ . Thus,
$\begin{align*} 6^{n!} &\equiv -1 \pmod{p}\\ 6^{2n!} & \equiv 1 \pmod{p} \end{align*}$ Hence, $\text{ord}_p(6)\mid 2n!$ but $\text{ord}_p(6) \nmid n!$ implying that $\nu_2(\text{ord}_p(6)) = \nu_2(n!)+1$ . But then, since $\text{ord}_p(6) \mid p-1$ ,
$\nu_2(p-1) \ge \nu_2(\text{ord}_p(6)) \ge \nu_2(n!)+1$ Thus, $p-1 \ge 2^{\nu_2(n!)+1}$ . But note that this implies,
$d \ge p \ge 2^{\nu_2(n!)+1}+1 \ge 2^{1+\lfloor \frac{n}{2}\rfloor+ \lfloor \frac{n}{4} \rfloor + \dots }+1 \ge 2^{2+\lfloor\frac{n}{2}\rfloor}+1$ by Legendre's Formula since $n \ge 6$ (so $\frac{n}{4}>1$ ).

However,
$d \ge 2^{2+\lfloor \frac{n}{2} \rfloor}+1 > 2^{\frac{n+3}{2}}> 2(n+3)$ since it is easy to see that $2^{\frac{n+3}{2}} > 2(n+3)$ for all $n \ge 6$ which is indeed the desired result.

Z K Y

The post below has been deleted. Click to close.

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

55 posts

#4 h May 1, 2025, 7:50 PM

Y by

Let $p \mid d \mid 6^{n!} +1$ ; be a prime.
First of all $p = 2,3$ obviously doesn't work.
When $p = 5$ , $6^{n!} + 1 \equiv 2(\text{ mod }5 )$ . $\therefore p\neq 5$ as well.
$6^{n!} \equiv -1 (\text{mod }p)$ $6^{2n!} \equiv 1 (\text{mod }p)$ Let $ord_{p}6 = a. \implies a\mid 2n!, a\nmid n!$ . $\implies v_2(a) = v_2(n!) + 1$ .
From Fermat's Little theorem, $a \mid p-1$
$v_2(p-1) \geq v_2(a) = v_2(n!) +1,$ Thus eliminating $a$ . Let $v_2(n!) = x ; x\in\mathbb{Z^{+}}$ . Then $p-1\geq 2^{x+1}y$ ; $y\in\mathbb{Z^+}$
From Legendre's
$v_2(n!) = \sum_{i = 1}^{\infty} \lfloor{\frac{n}{2^i}}\rfloor$ $\therefore p-1 \geq 2^{\sum_{i = 1}^{\infty} \lfloor{\frac{n}{2^i}}\rfloor} y$ As $n\geq 6$
$p-1 \geq 2^{1+\lfloor{\frac{n}{2}}\rfloor + \lfloor{\frac{n}{4}}\rfloor}y$ $\geq 2^{\frac{3n-1}{4}}y$ As $\lfloor{\frac{n}{4}}\rfloor \geq \frac{n-3}{4}, \lfloor{\frac{n}{2}}\rfloor \geq \frac{n-1}{2}.$

We can see that when $n\geq6, 2^{\frac{3n-1}{4}}\geq 2n+6$
$\therefore p-1 \geq 2^{\frac{3n-1}{4}}y > 2n+6$ $d \geq p > 2n +6$

Z K Y

The post below has been deleted. Click to close.

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

415 posts

#5 h May 1, 2025, 9:06 PM

Y by

Cute problem

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a