nyuuzyou/wikis huggingface dataset:
Henry Ernest Dudeney/Puzzles and Curious Problems/99 - The Conspirators' Code/Solution

== by : $99$ ==
;The Conspirators' Code
== Solution ==
 5 9 8
 5 0 7
+ 8 0 4 7
-----------
 9 1 5 2
== Proof ==
For each place value, the carry can only be $0, 1$ or $2$.
Let the carries from the units, tens and hundreds be $c_1, c_2$ and $c_3$ respectively.
We are given that $O = 0$ and $I = 1$.
So from the hundreds column we have:
:$F + F + 0 + c_2 \equiv 1 \pmod {10}$
Since the left hand side is an odd number:
:$c_2 = 1$
and thus $2 F \equiv 0 \pmod {10}$.
Since $F \ne 0$, we must have $F = 5$.
This gives $c_3 = 1$, and thus $Y + 1 = L$.
From $c_2 = 1$ we also have, in the tens column:
:$L + U + c_1 = 15$
so:
:$L = 15 - U - c_1 \ge 15 - 9 - 2 = 4$
We test each possible value of $L$.
Suppose $L = 4$.
Then $Y = 3$, $U = 9$ and $c_1 = 2$.
From the units column:
:$3 + R + R \ge 20$
:$R \ge 8.5$
but since the value of $9$ is taken by $U$, this is impossible.
Thus $L > 4$.
Since the value of $5$ is taken by $F$:
:$L \ne 5, 6$
Suppose $L = 7$.
Then $Y = 6$.
From the tens column:
:$7 + U + c_1 = 15$
Since $c_1$ can take on $0, 1, 2$:
:$U = 8, 7, 6$
but both $6$ and $7$ are taken.
Thus $U = 8$ and $c_1 = 0$.
From the units column:
:$6 + R + R = E < 10$
This gives $R = 1$ but $1$ is also taken.
Thus we cannot have $L = 7$.
Suppose $L = 8$.
Then $Y = 7$.
From the tens column:
:$8 + U + c_1 = 15$
Since $c_1$ can take on $0, 1, 2$:
:$U = 7, 6, 5$
but both $5$ and $7$ are taken.
Thus $U = 6$ and $c_1 = 1$.
From the units column:
:$7 + R + R = 10 + E$
The possible values of $R$ are $2, 3, 4, 9$.
But:
:$7 + 2 + 2 = 11$
:$7 + 3 + 3 = 13$
:$7 + 4 + 4 = 15$
:$7 + 9 + 9 = 25$
and all these possibities will use the same digit twice.
Thus $L \ne 8$.
Now we arrive at $L = 9$.
So we have $Y = 8$.
From the units column:
:$10 c_1 + E = 8 + R + R > 8 + 1 + 1 = 10$
so $c_1 \ge 1$.
From the tens column:
:$9 + U + c_1 = 15$
Since $c_1$ can take on $1$ and $2$:
:$U = 5, 4$
but $5$ is taken by $F$, so $U = 4$ and $c_1 = 2$.
Since $0$ is taken by $O$:
:$8 + R + R > 20$
This gives $R > 6$.
Since both $8$ and $9$ are taken, we must have $R = 7$ and thus $E = 2$.
Hence we arrive at the solution:
 5 9 8
 5 0 7
+ 8 0 4 7
-----------
 9 1 5 2
== Sources ==
* : Solutions: $99$. -- The Conspirators' Code
* : Answers: $158$. The Conspirators' Code
Category:Henry Ernest Dudeney/Puzzles and Curious Problems/Solutions
Henry Ernest Dudeney/Puzzles and Curious Problems/9 - Pocket-Money

== by : $9$ ==
;Pocket-Money
:"When I got to the station this morning," said Harold Tompkins, at his club, "I found I was short of cash.
:I spend just one-half of what I had on my railway ticket, and then bought a penny newspaper.
:When I got to the terminus I spent half of what I had left and twopence more on a telegram.
:Then I spent half of the remainder on a bus, and gave threepence to that old match-seller outside the club.
:Consequently I arrive here with this single penny.
:Now, how much did I start out with?"
=== Click here for solution ===
== Sources ==
* : Arithmetical and Algebraical Problems: Money Puzzles: $9$. -- Pocket-Money
* : Arithmetical and Algebraical Problems: Money Puzzles: $17$. Pocket Money
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/9 - Pocket-Money/Solution

== by : $9$ ==
;Pocket-Money
== Solution ==
:$3 \shillings 6 \oldpence$
== Proof ==
Tompkins ended up with $1 \oldpence$
Before he paid $3 \oldpence$ to the matchseller, he had $4 \oldpence$
Before spending half of what he had on a bus, he had $8 \oldpence$
Before spending $2 \oldpence$ on a telegram he had $10 \oldpence$
Before spending half of what he had left, he had $20 \oldpence$
Before buying a penny newspaper, he had $21 \oldpence$
Before spending half of what he had on a train ticket, he had $42 \oldpence$
That is, he started with $3 \shillings 6 \oldpence$
== Sources ==
* : Solutions: $9$. -- Pocket-Money
* : Answers: $17$. Pocket Money
Category:Henry Ernest Dudeney/Puzzles and Curious Problems/Solutions
Henry Ernest Dudeney/Puzzles and Curious Problems/Arithmetical and Algebraical Problems

== : : Arithmetical and Algebraical Problems ==
=== Money Puzzles ===
=== Age and Kinship Puzzles ===
=== Clock Puzzles ===
=== Locomotion and Speed Puzzles ===
=== Digital Puzzles ===
=== Various Arithmetical and Algebraical Problems ===
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Arithmetical and Algebraical Problems/Age and Kinship Puzzles

== : : Arithmetical and Algebraical Problems ==
==== $38$ - The Picnic ====
==== $39$ - Surprising Relationship ====
==== $40$ - An Epitaph (A.D. $1538$) ====
==== $41$ - Ancient Problem ====
==== $42$ - Family Ages ====
==== $43$ - Mike's Age ====
==== $44$ - Their Ages ====
==== $45$ - Brother and Sister ====
==== $46$ - A Square Family ====
==== $47$ - The Quarrelsome Children ====
==== $48$ - Robinson's Age ====
==== $49$ - The Engine-Driver's Name ====
==== $50$ - Buying Ribbon ====
==== $51$ - Sharing the Apples ====
==== $52$ - In the Year $1900$ ====
==== $53$ - Finding a Birthday ====
==== $54$ - The Birth of Boadicea ====
==== $55$ - Eliza's Surname ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Arithmetical and Algebraical Problems/Clock Puzzles

== : : Arithmetical and Algebraical Problems ==
==== $56$ - The Ambiguous Clock ====
==== $57$ - The Broken Clock Face ====
==== $58$ - When did the Dancing Begin? ====
==== $59$ - Mistaking the Hands ====
==== $60$ - Equal Distances ====
==== $61$ - Right and Left ====
==== $62$ - At Right Angles ====
==== $63$ - Westminster Clock ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Arithmetical and Algebraical Problems/Digital Puzzles

== : : Arithmetical and Algebraical Problems ==
==== $83$ - Three Different Digits ====
==== $84$ - Find the Cube ====
==== $85$ - Squares and Triangulars ====
==== $86$ - Digits and Cubes ====
==== $87$ - Reversing the Digits ====
==== $88$ - Digital Progression ====
==== $89$ - Forming Whole Numbers ====
==== $90$ - Summing the Digits ====
==== $91$ - Squaring the Digits ====
==== $92$ - Digits and Squares ====
==== $93$ - Figures for Letters ====
==== $94$ - Simple Multiplication ====
==== $95$ - Beeswax ====
==== $96$ - Wrong to Right ====
==== $97$ - Letter Multiplication ====
==== $98$ - Digital Money ====
==== $99$ - The Conspirators' Code ====
==== $100$ - Digital Squares ====
==== $101$ - Finding a Square ====
==== $102$ - Juggling with Digits ====
==== $103$ - Expressing Twenty-Four ====
==== $104$ - Letter-Figure Puzzle ====
==== $105$ - Equal Fractions ====
==== $106$ - Digits and Primes ====
==== $107$ - A Square of Digits ====
==== $108$ - The Nine Digits ====
==== $109$ - Perfect Squares ====
==== $110$ - An Absolute Skeleton ====
==== $111$ - Odds and Evens ====
==== $112$ - Simple Division ====
==== $113$ - A Complete Skeleton ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Arithmetical and Algebraical Problems/Locomotion and Speed Puzzles

== : : Arithmetical and Algebraical Problems ==
==== $64$ - The Bath Chair ====
==== $65$ - The Pedestrian Passenger ====
==== $66$ - Meeting Trains ====
==== $67$ - Carrying Bags ====
==== $68$ - The Moving Staircase ====
==== $69$ - The Four Cyclists ====
==== $70$ - The Donkey Cart ====
==== $71$ - The Three Motor-Cars ====
==== $72$ - The Fly and the Motor-Cars ====
==== $73$ - The Tube Stairs ====
==== $74$ - The Omnibus Ride ====
==== $75$ - A Question of Transport ====
==== $76$ - How Far Was It? ====
==== $77$ - Out and Home ====
==== $78$ - The Meeting Cars ====
==== $79$ - A Cycle Race ====
==== $80$ - A Little Train Puzzle ====
==== $81$ - An Irish Jaunt ====
==== $82$ - A Walking Problem ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Arithmetical and Algebraical Problems/Money Puzzles

== : : Arithmetical and Algebraical Problems ==
==== $1$ - The Money Bag ====
==== $2$ - A Legacy Puzzle ====
==== $3$ - Buying Toys ====
==== $4$ - Puzzling Legacies ====
==== $5$ - Dividing the Legacy ====
==== $6$ - A New Partner ====
==== $7$ - Squaring Pocket-Money ====
==== $8$ - Equal Values ====
==== $9$ - Pocket-Money ====
==== $10$ - Mental Arithmetic ====
==== $11$ - Distribution ====
==== $12$ - Reductions in Price ====
==== $13$ - The Three Hospitals ====
==== $14$ - Horses and Bullocks ====
==== $15$ - Buying Turkeys ====
==== $16$ - The Thrifty Grocer ====
==== $17$ - The Missing Penny ====
==== $18$ - The Red Death League ====
==== $19$ - A Poultry Poser ====
==== $20$ - Boys and Girls ====
==== $21$ - The Cost of a Suit ====
==== $22$ - The War Horse ====
==== $23$ - A Deal in Cucumbers ====
==== $24$ - The Two Turkeys ====
==== $25$ - Flooring Figures ====
==== $26$ - Cross and Coins ====
==== $27$ - Buying Tobacco ====
==== $28$ - A Farthings Puzzle ====
==== $29$ - The Shopkeeper's Puzzle ====
==== $30$ - Subscriptions ====
==== $31$ - A Queer Settling Up ====
==== $32$ - Apple Transactions ====
==== $33$ - Prosperous Business ====
==== $34$ - The Banker and the Note ====
==== $35$ - The Reapers' Puzzle ====
==== $36$ - The Flagons of Wine ====
==== $37$ - A Wages Paradox ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Arithmetical and Algebraical Problems/Various Arithmetical and Algebraical Problems

== : : Arithmetical and Algebraical Problems ==
==== $114$ - Elementary Arithmetic ====
==== $115$ - The Eight Cards ====
==== $116$ - Transferring the Figures ====
==== $117$ - A Queer Addition ====
==== $118$ - Six Simple Questions ====
==== $119$ - The Three Drovers ====
==== $120$ - Proportional Representation ====
==== $121$ - Find the Numbers ====
==== $122$ - A Question of Cubes ====
==== $123$ - Two Cubes ====
==== $124$ - Cube Differences ====
==== $125$ - Accommodating Squares ====
==== $126$ - Making Squares ====
==== $127$ - Find the Squares ====
==== $128$ - Forming Squares ====
==== $129$ - Squares and Cubes ====
==== $130$ - Milk and Cream ====
==== $131$ - Feeding the Monkeys ====
==== $132$ - Sharing the Apples ====
==== $133$ - Sawing and Splitting ====
==== $134$ - The Bag of Nuts ====
==== $135$ - Distributing Nuts ====
==== $136$ - Juvenile Highwaymen ====
==== $137$ - Buying Dog Biscuits ====
==== $138$ - The Three Workmen ====
==== $139$ - Working Alone ====
==== $140$ - A Curious Progression ====
==== $141$ - The First "Boomerang" Puzzle ====
==== $142$ - Longfellow's Bees ====
==== $143$ - "Lilivati", A.D. $1150$ ====
==== $144$ - Biblical Arithmetic ====
==== $145$ - The Printer's Problem ====
==== $146$ - The Swarm of Bees ====
==== $147$ - Blindness in Bats ====
==== $148$ - A Menagerie ====
==== $149$ - Sheep Stealing ====
==== $150$ - Sheep Sharing ====
==== $151$ - The Arithmetical Cabby ====
==== $152$ - The Length of a Lease ====
==== $153$ - A Military Puzzle ====
==== $154$ - Marching an Army ====
==== $155$ - The Orchard Problem ====
==== $156$ - Multiplying the Nine Digits ====
==== $157$ - Counting the Matches ====
==== $158$ - Newsboys ====
==== $159$ - The Year $1927$ ====
==== $160$ - Boxes of Cordite ====
==== $161$ - Blocks and Squares ====
==== $162$ - Find the Triangle ====
==== $163$ - Domino Fractions ====
==== $164$ - Cow, Goat and Goose ====
==== $165$ - The Postage-Stamps Puzzle ====
==== $166$ - Hens and Tens ====
==== $167$ - The Cancelled Cheque ====
==== $168$ - Mental Arithmetic ====
==== $169$ - Shooting Blackbirds ====
==== $170$ - The Six Noughts ====
==== $171$ - Multiplication Dates ====
==== $172$ - Curious Multiplicand ====
==== $173$ - Short Cuts ====
==== $174$ - More Curious Multiplication ====
==== $175$ - Cross-Number Puzzle ====
==== $176$ - Counting the Loss ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Combination and Group Problems

== : : Combination and Group Problems ==
==== $273$ - City Luncheons ====
==== $274$ - Halfpennies and Tray ====
==== $275$ - The Necklace Problem ====
==== $276$ - An Effervescent Puzzle ====
==== $277$ - Tessellated Tiles ====
==== $278$ - The Thirty-Six Letter Puzzle ====
==== $279$ - Roses, Shamrocks, and Thistles ====
==== $280$ - The Ten Barrels ====
==== $281$ - A Match Puzzle ====
==== $282$ - The Magic Hexagon ====
==== $283$ - Pat in Africa ====
==== $284$ - Lamp Signalling ====
==== $285$ - The Teashop Check ====
==== $286$ - Unlucky Breakdowns ====
==== $287$ - The Handcuffed Prisoners ====
==== $288$ - Seating the Party ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Crossing River Problem, and Problems Concerning Games and Puzzle Games

== : : Crossing River Problem, and Problems Concerning Games and Puzzle Games ==
==== $303$ - Crossing the River ====
==== $304$ - Grasshoppers' Quadrille ====
==== $305$ - Domino Frames ====
==== $306$ - A Puzzle in Billiards ====
==== $307$ - Scoring at Billiards ====
==== $308$ - Domino Hollow Squares ====
==== $309$ - Domino Sequences ====
==== $310$ - Two Domino Squares ====
==== $311$ - Domino Multiplication ====
==== $312$ - Domino Rectangle ====
==== $313$ - The Domino Column ====
==== $314$ - Card Shuffling ====
==== $315$ - Arranging the Dominoes ====
==== $316$ - Queer Golf ====
==== $317$ - The Archery Match ====
==== $318$ - Target Practice ====
==== $319$ - The Ten Cards ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Geometrical Problems/Dissection Puzzles

== : : Geometrical Problems: Dissection Puzzles ==
==== $177$ - Square of Squares ====
==== $178$ - Stars and Crosses ====
==== $179$ - Greek Cross Puzzle ====
==== $180$ - Square and Cross ====
==== $181$ - Three Greek Crosses from One ====
==== $182$ - Making a Square ====
==== $183$ - Table-Top and Stools ====
==== $184$ - Dissecting the Letter E ====
==== $185$ - The Dissected Chessboard ====
==== $186$ - Triangle and Square ====
==== $187$ - Changing the Suit ====
==== $188$ - Squaring the Circle ====
==== $189$ - Problem of the Extra Cell ====
==== $190$ - A Horseshoe Puzzle ====
==== $191$ - Two Squares in One ====
==== $192$ - The Submarine Net ====
==== $193$ - Square Table-Top ====
==== $194$ - Cutting the Veneer ====
==== $195$ - Improvised Chessboard ====
==== $196$ - The Four Stars ====
==== $197$ - Economical Dissection ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Geometrical Problems/Various Geometrical Puzzles

== : : Geometrical Problems: Various Geometrical Puzzles ==
==== $200$ - Measuring the River ====
==== $201$ - Square and Triangle ====
==== $202$ - A Garden Puzzle ====
==== $203$ - A Triangle Puzzle ====
==== $204$ - The Donjon Keep Window ====
==== $205$ - The Square Window ====
==== $206$ - The Triangular Plantation ====
==== $207$ - Six Straight Fences ====
==== $208$ - Dividing the Board ====
==== $209$ - A Running Puzzle ====
==== $210$ - Pat and his Pig ====
==== $211$ - The Twenty Matches ====
==== $212$ - Transplanting the Trees ====
==== $213$ - A Swastikaland Map ====
==== $214$ - Colouring the Map ====
==== $215$ - The Damaged Rug ====
==== $216$ - The Four Householders ====
==== $217$ - The Three Fences ====
==== $218$ - The Farmer's Sons ====
==== $219$ - The Three Tablecloths ====
==== $220$ - The Five Fences ====
==== $221$ - The Fly's Journey ====
==== $222$ - Folding a Pentagon ====
==== $223$ - The Tower of Pisa ====
==== $224$ - The Tank Puzzle ====
==== $225$ - An Artist's Puzzle ====
==== $226$ - The Circulating Motor-Car ====
==== $227$ - A Match-Boarding Order ====
==== $228$ - The Ladder ====
==== $229$ - Geometrical Progression ====
==== $230$ - In a Garden ====
==== $231$ - The Rose Garden ====
==== $232$ - A Pavement Puzzle ====
==== $233$ - The Nougat Puzzle ====
==== $234$ - Pile Driving ====
==== $235$ - An Easter Egg Problem ====
==== $236$ - The Pedestal Puzzle ====
==== $237$ - The Mudbury War Memorial ====
==== $238$ - A Maypole Puzzle ====
==== $239$ - The Bell Rope ====
==== $240$ - Counting the Triangles ====
==== $241$ - A Hurdles Puzzle ====
==== $242$ - Correcting a Blunder ====
==== $243$ - The Squirrel's Climb ====
==== $244$ - Sharing a Grindstone ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Magic Square, Measuring, Weighing, and Packing Problems

== : : Magic Square, Measuring, Weighing, and Packing Problems ==
==== $289$ - Magic Square Trick ====
==== $290$ - A Four-Figure Magic Square ====
==== $291$ - Progressive Squares ====
==== $292$ - Conditional Magic Square ====
==== $293$ - The Twenty Pennies ====
==== $294$ - The Keg of Wine ====
==== $295$ - Blending the Teas ====
==== $296$ - Water Measurement ====
==== $297$ - Mixing the Wine ====
==== $298$ - The Stolen Balsam ====
==== $299$ - The Weight of the Fish ====
==== $300$ - Fresh Fruits ====
==== $301$ - Weighing the Tea ====
==== $302$ - Delivering the Milk ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Moving Counter Problems

== : : Moving Counter Problems ==
==== $245$ - Magic Fifteen Puzzle ====
==== $246$ - Transferring the Counters ====
==== $247$ - The Counter Cross ====
==== $248$ - Four in Line ====
==== $249$ - Odds and Evens ====
==== $250$ - Adjusting the Counters ====
==== $251$ - Nine Men in a Trench ====
==== $252$ - Black and White ====
==== $253$ - The Angelica Puzzle ====
==== $254$ - The Flanders Wheel ====
==== $255$ - A Peg Puzzle ====
==== $256$ - Catching the Prisoners ====
==== $257$ - Five Lines of Four ====
==== $258$ - Deploying Battleships ====
==== $259$ - Flies on Window Panes ====
==== $260$ - Stepping Stones ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Unclassified Problems

== : : Unclassified Problems ==
==== $320$ - An Awkward Time ====
==== $321$ - Cryptic Addition ====
==== $322$ - The New Gun ====
==== $323$ - Cats and Mice ====
==== $324$ - The Two Snakes ====
==== $325$ - The Price of a Garden ====
==== $326$ - Strange Though True ====
==== $327$ - Two Paradoxes ====
==== $328$ - Choosing a Site ====
==== $329$ - The Four Pennies ====
==== $330$ - The Encircled Triangles ====
==== $331$ - The Siamese Serpent ====
==== $332$ - A Bunch of Grapes ====
==== $333$ - A Hopscotch Puzzle ====
==== $334$ - A Little Match Trick ====
==== $335$ - Three Times the Size ====
==== $336$ - A Six-Sided Figure ====
==== $337$ - Twenty-Six Matches ====
==== $338$ - The Three Matches ====
==== $339$ - Equilateral Triangles ====
==== $340$ - Squares with Matches ====
==== $341$ - Hexagon to Diamonds ====
==== $342$ - A Wily Puzzle ====
==== $343$ - Tom Tiddler's Ground ====
==== $344$ - Coin and Hole ====
==== $345$ - The Egg Cabinet ====
==== $346$ - A Leap Year Puzzle ====
==== $347$ - The Iron Chain ====
==== $348$ - Blowing Out the Candle ====
==== $349$ - Releasing the Stick ====
==== $350$ - The Keys and Ring ====
==== $351$ - The Entangled Scissors ====
==== $352$ - Locating the Coins ====
==== $353$ - The Three Sugar Basins ====
==== $354$ - The Wheels of the Car ====
==== $355$ - The Seven Children ====
==== $356$ - A Rail Problem ====
==== $357$ - The Wheel Puzzle ====
==== $358$ - Simple Addition ====
==== $359$ - Queer Arithmetic ====
==== $360$ - Fort Garrisons ====
==== $361$ - Constellation Puzzle ====
==== $362$ - Intelligence Tests ====
==== $363$ - At the Mountain Top ====
==== $364$ - Cupid's Arithmetic ====
==== $365$ - Tangrams ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Henry Ernest Dudeney/Puzzles and Curious Problems/Unicursal and Route Problems

== : : Unicursal and Route Problems ==
==== $261$ - The Twenty-Two Bridges ====
==== $262$ - A Monmouth Tombstone ====
==== $263$ - Footprints in the Snow ====
==== $264$ - The Fly's Tour ====
==== $265$ - Inspecting the Roads ====
==== $266$ - Railway Routes ====
==== $267$ - A Motor-Car Tour ====
==== $268$ - Mrs. Simper's Holiday Tour ====
==== $269$ - Sixteen Straight Runs ====
==== $270$ - Planning Tours ====
==== $271$ - Avoiding the Mines ====
==== $272$ - A Madam Problem ====
Category:Henry Ernest Dudeney/Puzzles and Curious Problems
Hensel's Lemma/First Form

== Theorem ==
Let $p$ be a prime number.
Let $k > 0$ be a positive integer.
Let $f \left({X}\right) \in \Z \left[{X}\right]$ be a polynomial.
Let $x_k \in \Z$ such that:
:$f \left({x_k}\right) \equiv 0 \pmod {p^k}$
:$f' \left({x_k}\right) \not \equiv 0 \pmod p$
Then for every integer $l \ge 0$, there exists an integer $x_{k + l}$ such that:
:$f \left({x_{k + l} }\right) \equiv 0 \pmod {p^{k + l} }$
:$x_{k + l}\equiv x_k \pmod {p^k}$
and any two integers satisfying these congruences are congruent modulo $p^{k + l}$.
Moreover, for all $l\geq0$ and any solutions $x_{k + l}$ and $x_{k + l + 1}$:
:$x_{k + l + 1} \equiv x_{k + l} - \dfrac {f \left({x_{k + l} }\right)} {f' \left({x_{k + l} }\right)} \pmod {p^{k + l + 1} }$
:$x_{k + l + 1} \equiv x_{k + l} \pmod {p^{k + l} }$
== Proof ==
We use induction on $l$.
The base case $l = 0$ is trivial.
Let $l \ge 0$ be such that a solution $x_{k + l}$ exists and is unique up to a multiple of $p^{k + l}$.
Choose a solution $x_{k + l}$ satisfying:
:$f \left({x_{k + l} }\right) \equiv 0 \pmod {p^{k + l} }$
:$x_{k + l} \equiv x_k \pmod {p^k}$
By Congruence by Divisor of Modulus, each solution $x_{k + l + 1}$ is also a solution of the previous congruence.
By uniqueness, it has to satisfy $x_{k + l + 1}\equiv x_{k + l} \pmod {p^{k + l} }$, hence is of the form $x_{k+ l} + t p^{k + l}$ with $t \in \Z$.
Let $d = \deg f$.
We have, for all $t \in \Z$:
Because $f' \left({x_{k + l} }\right) \equiv f' \left({x_k}\right) \not \equiv 0 \pmod p$, $f' \left({x_{k + l} }\right)$ is invertible modulo $p$.
Thus $x_{k + l} + t p^{k + l}$ is a solution modulo $p^{k + l + 1}$ :
:$t \equiv - \dfrac {f \left({x_{k + l} }\right)} {f' \left({x_{k + l} }\right)} \pmod p$
Thus, necessarily:
:$x_{k + l + 1} \equiv x_{k + l} - \dfrac {f \left({x_{k + l} }\right)} {f' \left({x_{k + l} }\right)} \pmod {p^{k + l + 1} }$
which proves the existence and uniqueness.
By induction, we have shown uniqueness and existence for all $l \ge 0$, as well as the relations:
:$x_{k + l + 1} \equiv x_{k + l} - \dfrac {f \left({x_{k + l} }\right)} {f' \left({x_{k + l} }\right)} \pmod {p^{k + l + 1} }$
:$x_{k + l + 1} \equiv x_{k + l} \pmod {p^{k + l} }$
== Also see ==
* Hensel's Lemma for Composite Numbers
Category:Hensel's Lemma
Hensel's Lemma/P-adic Integers

== Theorem ==
Let $\Z_p$ be the $p$-adic integers for some prime $p$.
Let $\map F X \in \Z_p \sqbrk X$ be a polynomial.
Let $\map {F'} X$ be the (formal) derivative of $F$.
Let $p\Z_p$ denote the principal ideal of $\Z_p$ generated by $p$.
For all $x,y \in \Z_p$, let:
:$x \equiv y \pmod {p\Z_p}$
denote congruence modulo the principal ideal $p\Z_p$.
Let $\alpha_0 \in \Z_p$ be a $p$-adic integer:
:$\map F {\alpha_0} \equiv 0 \pmod {p\Z_p}$
:$\map {F'} {\alpha_0} \not\equiv 0 \pmod {p\Z_p}$
Then there exists a unique $\alpha \in \Z_p$:
:$\alpha \equiv \alpha_0 \pmod {p\Z_p}$
:$\map F {\alpha} = 0$
== Proof ==
=== Lemma 1 ===
Let:
:$\alpha = \ds \sum_{n = 0}^\infty d_n p^n$
=== Lemma 2 ===
From Characterization of Polynomial has Root in P-adic Integers:
:$\map F \alpha = 0$
== Sources ==
* : $\S 3.4$ Hensel's Lemma, Theorem $3.4.1$
* : $\S 1.7$ Hensel's Lemma and Congruences: Theorem $1.39$
Category:Hensel's Lemma