• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 16:13
CET 22:13
KST 06:13
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11[ASL22] Ro16 Preview: Holy Diver5
Community News
Weekly Cups (Nov 9-15): Clem and herO take over0Dark completes military service, returns to SC213[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
StarCraft open world shooter announced at BlizzCon Dark completes military service, returns to SC2 No more SC2 streamers on team liquid? Weekly Cups (Nov 9-15): Clem and herO take over Serral's getting trashed by New Catsle's Mind
Tourneys
RSL goes to London! 2026 Offline Finals Nov 21-22 Sparkling Tuna Cup - Weekly Open Tournament Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19) soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 552 Secret Storm The PondCast: SC2 News & Results Mutation # 551 Robotic Revival Mutation # 550 Graveyard Shift
Brood War
General
BW General Discussion NaDa's Body List of top players active on ShieldBattery Shield Battery Server New Patch BGH Auto Balance -> http://bghmmr.eu/
Tourneys
SC1 Kevin Scrim hosted by SOOP (Nov 18-19) [IPSL] Winter 26-27 Round of 16! [Megathread] Daily Proleagues 2v2v2v2 Tournament Stage 2: Players
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
Nintendo Switch Thread Stormgate/Frost Giant Megathread Free Space RTS Game, optimised f. Phone/Tablet etc List of Game Threads The PlayStation 5
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread Things Aren’t Peaceful in Palestine Russo-Ukrainian War Thread Artificial Intelligence Thread Trading/Investing Thread
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
TeamLiquid Health and Fitness Initiative For 2023 Football (Soccer) Thread
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Customize Sidebar...

Website Feedback

Closed Threads



Active: 14904 users

Math puzzle #2

Blogs > LastPrime
Post a Reply
1 2 Next All
LastPrime
Profile Blog Joined May 2010
United States109 Posts
Last Edited: 2010-09-10 01:42:33
September 09 2010 23:24 GMT
#1
Ok guys, the last puzzle was so easy my 7 year old sister could do it (it was her homework from her math class in kindergarten). Here's one for the grown ups:

Prove that for any positive integer d,there is an integer N for which d| 2^N+N. (means d divides 2^N+N evenly)


edit:
+ Show Spoiler +
Hint:
1) if gcd(2,n) = 1 then 2^(phi(n)) = 1 (mod n)
where phi(n) is the number of integers in {1,2,3,4,...n} that are relatively prime to n

2) Chinese remainder theorem


Hall of Fame
1. Steve496


Hidden_MotiveS
Profile Blog Joined February 2010
Canada2562 Posts
Last Edited: 2010-09-09 23:36:32
September 09 2010 23:29 GMT
#2
Spoilers+ Show Spoiler +
I give up


edit: working on it.
BottleAbuser
Profile Blog Joined December 2007
Korea (South)1888 Posts
Last Edited: 2010-09-10 00:11:28
September 09 2010 23:32 GMT
#3
Trivial solution: N = 0 works for all positive integers.

For powers of 2 (d = 2^k), d divides 2^k. It might not divide 2^k + k. However, we know that it divides all multiples of 2^k, including 2^(k+1), 2^(k+2), and so on, until we reach at most 2^(d). Then we know that d divides 2^d+d.


2^N % d = a.

Then 2^(N+1) % d = 2a % d
Then 2^(N+2) % d = 4a % d
And so on. If d is even, then eventually we'll find ka % d = 0, and multiples of that (N>k) can be used until the constant term +N comes around to a multiple of d.

time for classes... I'll give it another go later...
Compilers are like boyfriends, you miss a period and they go crazy on you.
Seth_
Profile Blog Joined July 2010
Belgium184 Posts
September 10 2010 00:38 GMT
#4
If d is even, then eventually we'll find ka % d = 0

d=6
start at N=2
2^2 % 6 = 4 = a
2^3 % 6 = 2
2^4 % 6 = 4
2^5 % 6 = 2
2^6 % 6 = 4
2^7 % 6 = 2
...
We'll never get to a 'k' for which ka%d=0
BottleAbuser
Profile Blog Joined December 2007
Korea (South)1888 Posts
Last Edited: 2010-09-10 01:03:21
September 10 2010 00:44 GMT
#5
I'm tempted to say that any loop is fine, because we're adding increments of 1 to the total modulus with each next term.

The point was that if 2^N % d = 0, then we can increment N until the remaining +N is also divisible by d.

If we can't increase 2^N to be divisible by d, then obviously we have entered a loop, over which we can keep increasing the remaining +N until the total is divisible by d.

If any loop is okay, then this should work for odd numbers as well.


====
to summarize

For any d, take an arbitrary N.

Let a = 2^N % d
Let b = N % d

If a + b = 0 or d, we are finished.

Now, we see if a * 2^k % d = 0 for any k. We need to increment k a maximum of d times before the modulus value begins looping or reaches 0.

In the case that it reaches 0, we only need to increment N a maximum of d more times before the value 2^N + N % d = 0.

In the case that it loops, we find the values of N where 2^(N+kb) % d = a. That is, the loop has a period of k numbers, and b is the number of total cycles. As long as k % d != 0, we can increment b until the constant added at the end matches up and the remainder becomes 0.

... I realize this still isn't proof to work for all numbers, just a lot of them...
Compilers are like boyfriends, you miss a period and they go crazy on you.
Exteray
Profile Blog Joined June 2007
United States1094 Posts
September 10 2010 01:32 GMT
#6
Need a hint... will Fermat's Little Theorem come in handy here?
BottleAbuser
Profile Blog Joined December 2007
Korea (South)1888 Posts
September 10 2010 01:39 GMT
#7
The proof for Fermat's Little Theorem looks like it could readily be adapted for this.
Compilers are like boyfriends, you miss a period and they go crazy on you.
LastPrime
Profile Blog Joined May 2010
United States109 Posts
Last Edited: 2010-09-10 01:42:47
September 10 2010 01:40 GMT
#8
Hint:
1) if gcd(2,n) = 1 then 2^(phi(n)) = 1 (mod n)
where phi(n) is the number of integers in {1,2,3,4,...n} that are relatively prime to n

2) Chinese remainder theorem

These are some of the standard tools for solving IMO-type problems.

Good luck!
Slithe
Profile Blog Joined February 2007
United States985 Posts
September 10 2010 01:59 GMT
#9
I kinda wanna take a crack at this problem, but it also kinda feels like I'm doing discrete math homework all over again.

I'll probably give it a bit of a shot and give up because I'm lame.
TanGeng
Profile Blog Joined January 2009
Sanya12364 Posts
September 10 2010 02:04 GMT
#10
I think we can start by looking when the modulus on 2^N repeats.

First start by expression d as
2^e * m where GCD(m, 2) = 1 and e is a non-negative integer
Candidate solutions will when N > e and is some multiple of 2^e. note GCD(m, 2^e) = 1

now when m = 1 we trivial solution
N = 2^e

by the Totient theorem will get repetitive modulo on phi(m)
because 2^phi(m) % m = 1
repetition is over values less than m and relatively prime to m (multiplied by 2^e)

Now for the totients:
for all primes t and positive integer n : phi(t^n) = t^(n-1)* (t-1)
for all positive integers p & q where GCD(p,q) = 1 : phi(p*q) = phi(p) * phi(q)

seems to get complicated from here on... hmmm
To be continued...
Moderator我们是个踏实的赞助商模式俱乐部
Slithe
Profile Blog Joined February 2007
United States985 Posts
September 10 2010 02:59 GMT
#11
I think I may have a solution for the odd numbers:

+ Show Spoiler +

for any odd d, N=d-1 will give us the desired result.

With the theorem that lastprime gave us, we see the following:
gcd(d,d-1) = 1
2^(d-1) = 1 mod d
2^(d-1) + d-1 = 0 mod d

I'm trying to use this to tackle the even numbers as well, with the idea that any even number d = c*(2^x). However, this is all pointless if my earlier conclusion is incorrect.
infinitestory
Profile Blog Joined April 2010
United States4053 Posts
September 10 2010 03:07 GMT
#12
I think this gets messy only because m could be even, which means we need to split into an odd case and an (even harder) even case, and phi(m) often shares factors with m, so looping by adding phi(m) isn't guaranteed to work.
Translator:3
Snuggles
Profile Blog Joined May 2010
United States1865 Posts
September 10 2010 03:11 GMT
#13
So are all of you guys math majors? This problem looks so intimidating I don't even want to touch it haha.
TanGeng
Profile Blog Joined January 2009
Sanya12364 Posts
Last Edited: 2010-09-10 03:24:49
September 10 2010 03:21 GMT
#14
On September 10 2010 11:59 Slithe wrote:
I think I may have a solution for the odd numbers:

+ Show Spoiler +

for any odd d, N=d-1 will give us the desired result.

With the theorem that lastprime gave us, we see the following:
gcd(d,d-1) = 1
2^(d-1) = 1 mod d
2^(d-1) + d-1 = 0 mod d

I'm trying to use this to tackle the even numbers as well, with the idea that any even number d = c*(2^x). However, this is all pointless if my earlier conclusion is incorrect.


Only true for prime numbers.

Even numbers aren't too bad. Just factor out the powers of 2 will be sufficient and that will reduce it to an odd number problem. Maybe I'm missing it but the non-prime odd values are the hardest part to solve.
Moderator我们是个踏实的赞助商模式俱乐部
Slithe
Profile Blog Joined February 2007
United States985 Posts
September 10 2010 03:37 GMT
#15
On September 10 2010 12:21 TanGeng wrote:
Show nested quote +
On September 10 2010 11:59 Slithe wrote:
I think I may have a solution for the odd numbers:

+ Show Spoiler +

for any odd d, N=d-1 will give us the desired result.

With the theorem that lastprime gave us, we see the following:
gcd(d,d-1) = 1
2^(d-1) = 1 mod d
2^(d-1) + d-1 = 0 mod d

I'm trying to use this to tackle the even numbers as well, with the idea that any even number d = c*(2^x). However, this is all pointless if my earlier conclusion is incorrect.


Only true for prime numbers.

Even numbers aren't too bad. Just factor out the powers of 2 will be sufficient and that will reduce it to an odd number problem. Maybe I'm missing it but the non-prime odd values are the hardest part to solve.


Oh I misread the theorem. Back to the drawing board...
mieda
Profile Blog Joined February 2010
United States85 Posts
Last Edited: 2010-09-10 19:18:27
September 10 2010 04:20 GMT
#16
If you need more hints let me know and I'll post some more hints here.

Edit: I suggested this problem to LastPrime for a little Math Puzzle Time in TL.net, so it'd defeat the purpose of me releasing my solution here. We'll post some harder ones once this is solved. Enjoy~

An easier version of this problem is the following: Every positive integer d divides 2^N - N for some N, in which case the idea of looking at cycles work, i.e. 2, 2^2, 2^(2^2), 2^(2^(2^2)), ... eventually becomes constant mod d for any positive integer d. In fact you can bound the cycle length, and get a rather nice expression for an explicit solution for N in terms of d.

Also, I'm on #math of efnet IRC and freenode, ID: hochs. If you want more lively math chat, I'm there and you can /msg me for some fun

Now back to preparing lecture notes for serre duality and its applications to riemann roch type theorems..
Steve496
Profile Joined July 2009
United States60 Posts
Last Edited: 2010-09-10 05:17:58
September 10 2010 05:17 GMT
#17
The solution is more or less obvious for powers of 2 and when d and phi(d) are relatively prime (which notably includes all primes). It's a little less clear to me how to extend the argument to deal with d and phi(d) having a common factor.

(As an aside, for those of you who like this sort of thing, I highly recommend Project Euler. Good times.)
Oracle
Profile Blog Joined May 2007
Canada411 Posts
September 10 2010 05:38 GMT
#18
Lol i had this EXACT problem in a Math 135 assignment at the university of waterloo last year
mieda
Profile Blog Joined February 2010
United States85 Posts
September 10 2010 05:40 GMT
#19
On September 10 2010 14:38 Oracle wrote:
Lol i had this EXACT problem in a Math 135 assignment at the university of waterloo last year


Oh, is that where it's from? ^^ It's a nice exercise in chinese remainder theorem
gondolin
Profile Blog Joined September 2007
France332 Posts
September 10 2010 06:30 GMT
#20
We may assume by the CRT that d=p^n, with p odd, the case p=2 being trivial.
Now by induction, there exist N such that 2^N+N=0 mod phi(d).
Write 2^N+N + k phi(d) =0.
Then 2^(N+k phi(d)) + (N + k phi(d)) = 2^N+N+k phi(d) = 0 mod p^n.
CQFD.


On September 10 2010 13:20 mieda wrote:
Now back to preparing lecture notes for serre duality and its applications to riemann roch type theorems..


Nice. Will you use it to prove the Hasse-Weil theorem on the zeta function of algebraic curve? From what I remember you can prove it without the classical proof from Weil with Jacobians by clever user of the Riemann-Roch (the hardest part being the Riemann hypothesis, with Jacobians you have the Rosati involution, here I don't remember how you do it).

By the way I infer from your signature that you are working on Complex Multiplication? That's one of the most beautiful area in Mathematics (according to Hilbert )!
1 2 Next All
Please log in or register to reply.
Live Events Refresh
Next event in 3h 48m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
RotterdaM 871
TKL 415
SteadfastSC 304
JuggernautJason61
StarCraft: Brood War
ZZZero.O 79
firebathero 77
Dota 2
Gorgc7055
420jenkins222
Heroes of the Storm
Liquid`Hasu643
Trikslyr85
Other Games
tarik_tv5179
Grubby2856
FrodaN2577
Liquid`RaSZi2030
Beastyqt510
B2W.Neo436
shahzam376
mouzStarbuck195
ArmadaUGS129
Pyrionflax113
C9.Mang0112
Organizations
Other Games
BasetradeTV140
[ Show 12 non-featured ]
StarCraft 2
• Hinosc 10
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• WagamamaTV470
League of Legends
• TFBlade948
Other Games
• imaqtpie1202
Upcoming Events
PiGosaur Cup
3h 48m
The PondCast
12h 48m
University League
12h 48m
LiuLi Cup
13h 48m
Rogue vs TBD
Maru vs TBD
OSC
18h 48m
Replay Cast
1d 1h
GSL
1d 14h
Maru vs Dark
Patches Events
1d 16h
OSC
1d 18h
Replay Cast
2 days
[ Show More ]
KCM Race Survival
2 days
Ultimate Battle
2 days
ZerO vs Bisu
RSL Revival
3 days
BSL
3 days
eOnzErG vs StRyKeR
Cross vs JDConan
RSL Revival
4 days
IPSL
4 days
Ret vs ggnore13
nOmaD vs Aether
BSL
4 days
Bonyth vs Doodle
Kyrie vs Jimin
Replay Cast
5 days
WardiTV Weekly
5 days
Kung Fu Cup
6 days
Solar vs Classic
ByuN vs SHIN
Liquipedia Results

Completed

Proleague 2026-11-16
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026

Upcoming

Sector 591
YSL S4
SC4ALL II: Brood War
NBSL 2026 Xiamen LAN
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.