Number Theory, Modular Arithmetic / Remainder Arithmetic
Modular Arithmetic (or Remainder Arithmetic) is a system where numbers 'wrap around' after reaching a certain value, the modulus. It deals with congruences and remainders. Questions involve solving equations in modular systems, finding powers modulo `n`, and applications in patterns or cryptography.
Divisibility Rules Euler's Theorem and Fermat's Little Theorem-
Finite Division
Find all integers x, y, z, w that satisfy `x^2+y^2=3z^2+3w^2 `.
Sources: -
Divisible by 13
All natural numbers from 1 to 2006 are written on a sheet of paper, and a series of operations is performed as described below. At each step, any number of numbers are deleted from the list and their sum is denoted by S. Instead of the deleted numbers, a single number is added, which is the remainder obtained from the division of S by 13. After some number of such steps, only two numbers remain on the paper. One of them is 100. Find the other number.
Sources:Topics:Number Theory -> Modular Arithmetic / Remainder Arithmetic Number Theory -> Division -> Parity (Even/Odd) Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence- Grossman Math Olympiad, 2006 Question 2
-
THE MILLIONAIRE'S PERPLEXITY
Mr. Morgan G. Bloomgarten, the millionaire, known in the States as the Clam King, had, for his sins, more money than he knew what to do with. It bored him. So he determined to persecute some of his poor but happy friends with it. They had never done him any harm, but he resolved to inoculate them with the "source of all evil." He therefore proposed to distribute a million dollars among them and watch them go rapidly to the bad. But he was a man of strange fancies and superstitions, and it was an inviolable rule with him never to make a gift that was not either one dollar or some power of seven—such as `7, 49, 343, 2,401`, which numbers of dollars are produced by simply multiplying sevens together. Another rule of his was that he would never give more than six persons exactly the same sum. Now, how was he to distribute the `1,000,000` dollars? You may distribute the money among as many people as you like, under the conditions given.Sources:Topics:Number Theory -> Modular Arithmetic / Remainder Arithmetic Arithmetic -> Division with Remainder- Amusements in Mathematics, Henry Ernest Dudeney Question 16
-
CATCHING THE MICE
"Play fair!" said the mice. "You know the rules of the game."
"Yes, I know the rules," said the cat. "I've got to go round and round the circle, in the direction that you are looking, and eat every thirteenth mouse, but I must keep the white mouse for a tit-bit at the finish. Thirteen is an unlucky number, but I will do my best to oblige you."
"Hurry up, then!" shouted the mice.
"Give a fellow time to think," said the cat. "I don't know which of you to start at. I must figure it out.
"While the cat was working out the puzzle he fell asleep, and, the spell being thus broken, the mice returned home in safety. At which mouse should the cat have started the count in order that the white mouse should be the last eaten?
When the reader has solved that little puzzle, here is a second one for him. What is the smallest number that the cat can count round and round the circle, if he must start at the white mouse (calling that "one" in the count) and still eat the white mouse last of all?
And as a third puzzle try to discover what is the smallest number that the cat can count round and round if she must start at the white mouse (calling that "one") and make the white mouse the third eaten.
Sources:- Amusements in Mathematics, Henry Ernest Dudeney Question 232
-
Question
Let a1, a2, ..., a101 be a permutation of 2, 3, 4, ..., 102. Find all permutations such that ai is divisible by i for all i.
Sources:Topics:Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures- Tournament of Towns, 1979-1980, Main, Spring Question 3
-
Question
Given two natural numbers `k` and `m` that differ only in the order of their digits (that is, one is obtained from the other by swapping the order of the digits).
a. Prove that the sum of the digits of `2k` is equal to the sum of the digits of `2m`.
b. Prove that if `k` and `m` are even, then the sum of the digits of \(k\over 2\) is equal to the sum of the digits of \({m \over 2}\).
c. Prove that the sum of the digits of `5k` is equal to the sum of the digits of `5m`.
-
Question
The number `458` is written on the board. In each single step, you are allowed to either multiply the number written on the board by `2`, or erase its last digit.
Is it possible to obtain the number `14` using these operations?
Sources:Topics:Arithmetic Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures -
Question
Is it possible for the sum of three natural numbers to be divisible by each of them?
Sources: -
Question
Prove that the difference of squares of two consecutive odd numbers is divisible by `8`.
Sources: -
Question
Prove that the product of three consecutive numbers is divisible by `6`.