Numbers Theory

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

Numbers Theory

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Iran 3rd round 2017 Numbers theory final exam-P3

The post below has been deleted. Click to close.

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

16 posts

Amin12

#1 h Aug 30, 2017, 11:25 AM • 2 Y

Y by Adventure10, Mango247

Let $n$ be a positive integer. Prove that there exists a poisitve integer $m$ such that
$7^n \mid 3^m+5^m-1$

This post has been edited 3 times. Last edited by Amin12, Aug 30, 2017, 11:27 AM

Z K Y

The post below has been deleted. Click to close.

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

4892 posts

#2 h Aug 30, 2017, 12:32 PM • 4 Y

Y by rightways, eazy_math, Adventure10, Mango247

https://artofproblemsolving.com/community/q2h1498365p8825819

Z K Y

The post below has been deleted. Click to close.

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

71 posts

#3 h Aug 16, 2018, 6:21 AM • 2 Y

Y by Adventure10, Mango247

Goodgood

Z K Y

The post below has been deleted. Click to close.

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

80 posts

#4 h Apr 26, 2019, 9:29 AM • 5 Y

Y by Pluto1708, AlastorMoody, fungarwai, ILOVEMYFAMILY, Adventure10

Let's prove that $m=7^{n - 1}$ satisfies the given condition. We have to prove $-1- 3^{m}-5^{m} \equiv 0 \pmod {7^{n}}$ , firstly, we claim that $-3^{m} \equiv 4^{m} \pmod {7^{n}}$ and $-5^{m} \equiv 2^{m} \pmod {7^{n}}$ . It's equivalent to proving $7^{n}$ divides $2^{m}+5^{m}, 3^{m}+4^{m}$ . Since $m$ is odd, using Lifting The Exponent we have $\nu_7(2^{m} + 5^{m}) = \nu_7(m) +\nu_7(2 + 5) = n$ so $7^{n}$ divides $2^{m} + 5^{m}$ . Similarly we can prove that $7^{n}$ divides $3^{m} + 4 ^ {m}$ .
Now it's left to show that we indeed have $1 + 2^{m} + 4^{m} \equiv 0 \pmod {7^{n}}$ . Since $1 + 2^{m} + 4 ^{m} = \dfrac{2 ^ {3m} - 1}{2^{m} - 1}$ , it's enough to prove that $7^{n}$ divides $2^{3m} - 1$ and $7$ doesn't divide $2^{m} - 1$ . Since order of $2$ mod $7$ is $3$ and $3$ doesn't divide $m=7^{n-1}$ , latter is obvious. Using Lifting The Exponent again, we have $\nu_7(2^{3m} - 1) = \nu_7(2^{3} -1) + \nu_7(m) = n$ . PS

Z K Y

The post below has been deleted. Click to close.

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

Shayan-TayefehIR

104 posts

Shayan-TayefehIR

#5 h Mar 6, 2023, 11:07 AM • 1 Y

Y by Mahdi_Mashayekhi

Ignore...

This post has been edited 1 time. Last edited by Shayan-TayefehIR, Apr 20, 2024, 7:46 PM

Z K Y

The post below has been deleted. Click to close.

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

trying_to_solve_br

191 posts

trying_to_solve_br

#6 h Jul 4, 2023, 9:00 PM • 2 Y

Y by GreatKillaOE, MS_asdfgzxcvb

Sketch of solution:

We show this by induction on $n$ . The base case is trivial. Suppose we have that for $n$ this is true. Now, let $m$ be the number for which this is true for $n$ , and suppose the remainder of $m$ modulo $7^{n-1}.6=\phi(7^n)$ is $c$ . Then we write $m=c+7^{n-1}.6.k$ , and notice that modulo $\phi(7^{n+1})$ , this assumes 7 values. Now we want to show that one of those values satisfy the induction hypothesis. To show this, we change the induction to another one that will implicate the first induction obviously:

For some fixed residue of $m$ modulo $\phi(7^{n-1})$ , the sums $3^m+5^m$ are different modulo $7^n$ and one of those is one.

Notice that because of the fixed residue, those sums achieve at maximum (actually exactly, which we will prove later) 7 distinct residues. We now proceed by induction. Suppose this is false for $n+1$ , and it is true for $n$ . Letting $m=c+7^{n-1}.6.k$ be the residue that generated 1 before, vary $k=1,2...,7$ .

Notice now that $x^{7^{n-1}.6}=y$ is a 7th root of unity of $y^7 - 1$ , and the sets of numbers that are those roots of units are $1,w,w^2,...,w^6$ . Also notice that if a number $w$ is a 7th "root of unity" modulo $7^n$ , then by LTE $w^7$ is the root of unity modulo $7^{n+1}$ , and this set is $1,w^7,...,w^{42}$ .

Back to the problem, suppose we have $3^m+5^m\equiv 3^n+5^n (mod 7^{n+1})$ , with $m,n$ being both numbers that generated residue 1 modulo $7^n$ , that is, both of them have the same residue $c$ mentioned before. Substituting $m=c+6.7^{n-1}.k,n=c+6.7^{n-1}.j$ , and $3^{7^{n-1}.6}$ by $w^7$ , and $5^{7^{n-1}.6}$ by $w^{7b}$ where $w$ is a root of unity modulo $7^n$ ; we get that after some manipulations:

$3^c(w^{7j}-w^{7k})\equiv 5^c(w^{7bk}-w^{7bj}) (mod 7^{n+1})$ Which after expanding $x^7-y^7$ and noticing that the ugly therms cut out because both of their exponents are complete residues mod 7, we would have that $3^c(w^j - w^k)\equiv 5^c(w^bk-w^bj)$ , but this is true mod $7^{n+1}$ , which implies it is true mod $7^n$ , which is a contradiction by the induction hypothesis on the sums being disjoint.

Now, notice that as we supposed there was a sum generating residue 1 mod $7^n$ , then notice the new residues will be $7^n.1+1,7^n.2+1,...,7^n.7+1$ , and as all the sums are disjoint, all those 7 values (including the last one) will be generated, concluding the induction hypothesis.

Nice one, the main step was recognising the root of unity from $7^n$ to $7^{n+1}$ .

This post has been edited 2 times. Last edited by trying_to_solve_br, Jul 4, 2023, 9:03 PM

Z K Y

The post below has been deleted. Click to close.

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

13 posts

#7 h Mar 3, 2025, 9:00 AM

Y by

I think will be better if we use Newton's binomial principle
First: Claim m is odd
3^m=3 2 6 4 5 1(mod 7)
5^m=5 4 6 2 3 1(mod 7)
Since 5^m+3^m=1(mod 7)
So m is 6k+1 or 6k+5 so m is odd
Then 5^m=(8-3)^m
8^m-m*8^(m-1)*3 and etc
Now we need to find m such that
7^n|8^m-1 and 7^n| m!/k!*(m-k)!
What is true if we take m=7^n*2 or something similar

Z K Y

The post below has been deleted. Click to close.

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

120 posts

#8 h Mar 3, 2025, 9:45 AM

Y by

I guess the wording is wrong. Because $(1;1)$ obviously works. I think it meant infinite amount of $m$

This post has been edited 1 time. Last edited by Sadigly, Mar 3, 2025, 9:45 AM

Z K Y

The post below has been deleted. Click to close.

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

5542 posts

#9 h Mar 3, 2025, 4:44 PM

Y by

Sadigly wrote:

I guess the wording is wrong. Because $(1;1)$ obviously works. I think it meant infinite amount of $m$

No, it asks you to show that such $m$ exists for every $n$ , so simply stating $(1,1)$ is not enough.

Z K Y

The post below has been deleted. Click to close.

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

50 posts

#10 h Mar 27, 2025, 4:32 AM

Y by

This is also N3 of the 2017 BMO shortlist

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a