1,000 נורות כבויות עומדות בשורה וממוספרות בכל המספרים הטבעיים מ-1 עד 1,000, לכל נורה מתג. אם לוחצים על המתג כשהנורה כבויה, היא תידלק, אם לוחצים על המתג כשהנורה דולקת, היא תכבה. באים 1,000 גמדים, ממוספרים אף הם מ-1 עד 1,000. תחילה עובר גמד מס' 1 ולוחץ על המתג לכל הנורות שמספרן מתחלק ב-1. שני עובר גמד מס' 2 ולוחץ על המתג בכל הנורות שמספרן מתחלק ב-2. כך עוברים כל הגמדים לפי סדר כך שהגמד ה-n לוחץ על המתגים של כל הנורות שמספרן מתחלק ב-n. לאחר שהגמד ה-1,000 מסיים את עבודתו, אילו נורות תהיינה דלוקות ולמה?
פתרון
מכיוון שהמצב התחילי של הנורות הוא כבוי, הרי שכדי שנורה תדלוק בסוף התהליך צריכים ללחוץ עליה מספר אי-זוגי של פעמים. כל גמד לוחץ על נורה אם מספרה מתחלק במספר של הגמד, ולכן נורה שנלחצה מספר אי-זוגי של פעמים מתחלקת במספר אי-זוגי של מספרים.
לאילו מספרים יש מספר אי-זוגי של מחלקים? פעולת הכפל היא פעולה בינארית, כלומר פעולה בין שני מספרים, מה שאומר שאם מספר טבעי מסוים מתחלק במספר טבעי אחר- הרי ש מתחלק גם ב-. מכאן יוצא, לכאורה, שלכל מספר יש מספר זוגי של מחלקים, אולם ישנם מספרים יוצאי דופן, המספרים האלה הם המספרים הריבועיים. לכל מספר ריבועי קיים מספר טבעי בעבורו מתקיים השוויון: . למספרים הריבועיים יש תמיד מספר אי-זוגי של מחלקים, משום שיש להם מחלק אחד שלא גורר קיומו של מחלק שכנגד.
לדוגמה: המספר 7 מחלק את המספר 28, ולכן 28 חייב גם להתחלק ב-4, כי 28/7=4. לעומת זאת, המספר 7 מחלק את המספר 49, אבל מכיוון ש: 49/7=7 יש ל-49 מספר אי-זוגי של מחלקים.
