Square-free problem + non-standard problem

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

Square-free problem + non-standard problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Bulgarian Autumn Math Competition 2024

The post below has been deleted. Click to close.

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

2 posts

#1 h Nov 21, 2024, 10:28 AM • 2 Y

Y by kiyoras_2001, Laan

$9.3$
A natural number is called square-free, if it is not divisible by the square of any prime number. For a natural number $a$ , we consider the number $f(a) = a^{a+1} + 1$ . Prove that:
a) if $a$ is even, then $f(a)$ is not square-free
b) there exist infinitely many odd $a$ for which $f(a)$ is not square-free

$9.4$
We will call a generalized $2n$ -parallelogram a convex polygon with $2n$ sides, so that, traversed consecutively, the $k$ th side is parallel and equal to the $(n+k)$ th side for $k=1, 2, ... , n$ . In a rectangular coordinate system, a generalized parallelogram is given with $50$ vertices, each with integer coordinates. Prove that its area is at least $300$ .

Z K Y

The post below has been deleted. Click to close.

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

60 posts

Laan

#2 h Nov 21, 2024, 3:25 PM

Y by

I have a solution for problem 9.3
$a)$ Consider $p$ is a prime factor of $a+1$ .
As $p|a+1$ and $a+1$ is an odd number, by LTE lenma, we have:
$v_p(a^{a+1}+1)=v_p(a+1)+v_p(a+1)=2.v_p(a+1) \ge 2$ (cause $p|a+1$ )
Therefore: $p^2|a^{a+1}+1$
$b)$ For wich $a=100k+57$ ,k is a natural number:
$f(a)=(100k+57)^{2(50k+29)}+1\equiv7^{2(50k+29)} +1\equiv (-1)+1\equiv0$ (mod $25$ )
Hence, there exist ifinitely many odd number a s.t $f(a)$ is not square-free.

Z K Y

The post below has been deleted. Click to close.

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

2 posts

#3 h Nov 21, 2024, 9:50 PM

Y by

Laan wrote:

I have a solution for problem 9.3
$a)$ Consider $p$ is a prime factor of $a+1$ .
As $p|a+1$ and $a+1$ is an odd number, by LTE lenma, we have:
$v_p(a^{a+1}+1)=v_p(a+1)+v_p(a+1)=2.v_p(a+1) \ge 2$ (cause $p|a+1$ )
Therefore: $p^2|a^{a+1}+1$
$b)$ For wich $a=100k+57$ ,k is a natural number:
$f(a)=(100k+57)^{2(50k+29)}+1\equiv7^{2(50k+29)} +1\equiv (-1)+1\equiv0$ (mod $25$ )
Hence, there exist ifinitely many odd number a s.t $f(a)$ is not square-free.

What is the motivation behind looking at mod 25?

Z K Y

The post below has been deleted. Click to close.

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

60 posts

Laan

#4 h Nov 22, 2024, 11:36 AM

Y by

PlayForFUn wrote:

Laan wrote:

I have a solution for problem 9.3
$a)$ Consider $p$ is a prime factor of $a+1$ .
As $p|a+1$ and $a+1$ is an odd number, by LTE lenma, we have:
$v_p(a^{a+1}+1)=v_p(a+1)+v_p(a+1)=2.v_p(a+1) \ge 2$ (cause $p|a+1$ )
Therefore: $p^2|a^{a+1}+1$
$b)$ For wich $a=100k+57$ ,k is a natural number:
$f(a)=(100k+57)^{2(50k+29)}+1\equiv7^{2(50k+29)} +1\equiv (-1)+1\equiv0$ (mod $25$ )
Hence, there exist ifinitely many odd number a s.t $f(a)$ is not square-free.

What is the motivation behind looking at mod 25?

You can see my thinking process.
$a$ is an odd number so there exists a natural number $q$ s.t: $a=2q+1$ .
I get: $f(2q+1)=(2q+1)^{2.(q+1)}+1=(4q^2+4q+1)^{q+1}+1$
Here I asume $q+1$ is odd then: $(4q^2+4q+1)+1| f(2q+1)$
At this point, I search for which $q$ that $4q^2+4q+2$ has a square factor.
And I see that if $q \equiv 3$ (mod $25$ ) then $25|4q^2+4q+2$ . You can choose other modulo if you want.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a