Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [elementary-number-theory]

Questions on congruences, linear Diophantine equations, greatest common divisor, divisibility, etc.

332
votes
18answers
36k views

Find five positive integers whose reciprocals sum to $1$

Find a positive integer solution $(x,y,z,a,b)$ for which $$\frac{1}{x}+ \frac{1}{y} + \frac{1}{z} + \frac{1}{a} + \frac{1}{b} = 1\;.$$ Is your answer the only solution? If so, show why. I was ...
217
votes
6answers
9k views

Can you answer my son's fourth-grade homework question: Which numbers are prime, have digits adding to ten and have a three in the tens place?

My son Horatio (nine years old, fourth grade) came home with some fun math homework exercises today. One of his problems was the following little question: I am thinking of a number... It ...
215
votes
4answers
9k views

How many fours are needed to represent numbers up to $N$?

The goal of the four fours puzzle is to represent each natural number using four copies of the digit $4$ and common mathematical symbols. For example, $165=\left(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}...
182
votes
9answers
8k views

What does $2^x$ really mean when $x$ is not an integer?

We all know that $2^5$ means $2\times 2\times 2\times 2\times 2 = 32$, but what does $2^\pi$ mean? How is it possible to calculate that without using a calculator? I am really curious about this, so ...
176
votes
1answer
22k views

Are 14 and 21 the only “interesting” numbers?

The numbers 14 and 21 are quite interesting. The prime factorisation of 14 is $2\cdot 7$ and the prime factorisation of $14+1$ is $3\cdot 5$. Note that 3 is the prime after 2 and 5 is the prime ...
159
votes
6answers
26k views

Deleting any digit yields a prime… is there a name for this?

My son likes his grilled cheese sandwich cut into various numbers, the number depends on his mood. His mother won't indulge his requests, but I often will. Here is the day he wanted 100: But ...
130
votes
6answers
6k views

Do Arithmetic Mean and Geometric Mean of Prime Numbers converge?

I was looking at a list of primes. I noticed that $ \frac{AM (p_1, p_2, \ldots, p_n)}{p_n}$ seemed to converge. This led me to try $ \frac{GM (p_1, p_2, \ldots, p_n)}{p_n}$ which also seemed to ...
124
votes
7answers
23k views

Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$

For all $a, m, n \in \mathbb{Z}^+$, $$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$
113
votes
14answers
55k views

Why is 1 not a prime number?

Why is $1$ not considered a prime number? Or, why is the definition of prime numbers given for integers greater than $1$?
110
votes
7answers
24k views

Do we have negative prime numbers?

Do we have negative prime numbers? $..., -7, -5, -3, -2, ...$
102
votes
15answers
15k views

What is the smallest unknown natural number?

There are several unknown numbers in mathematics, such as optimal constants in some inequalities. Often it is enough to some estimates for these numbers from above and below, but finding the exact ...
102
votes
5answers
9k views

A multiplication algorithm found in a book by Paul Erdős: how does it work?

I am trying to understand the following problem from Erdős and Surányi's Topics in the theory of numbers (Springer), chapter 1 ("Divisibility, the Fundamental Theorem of Number Theory"): We can ...
97
votes
4answers
110k views

How to find solutions of linear Diophantine ax + by = c?

I want to find a set of integer solutions of Diophantine equation: $ax + by = c$, and apparently $\gcd(a,b)|c$. Then by what formula can I use to find $x$ and $y$ ? I tried to play around with it: $...
94
votes
11answers
29k views

Is zero odd or even?

Some books say even numbers start from two but if you consider the number line concept, I think zero ($0$) should be even because it is in between $-1$ and $+1$ (i.e in between two odd numbers). What ...
90
votes
11answers
17k views

Am I just not smart enough? [closed]

When I was doing math, let us say for example, introductory number theory, it seems to take me a lot of time to fully understand a theorem. By understanding, I mean, both intuitively and also ...
89
votes
1answer
4k views

$4494410$ and friends

The number $4494410$ has the property that when converted to base $16$ it is $44944A_{16}$, then if the $A$ is expanded to $10$ in the string we get back the original number. $3883544142410_{10}=...
88
votes
2answers
4k views

Help me put these enormous numbers in order: googol, googol-plex-bang, googol-stack and so on

Popular mathematics folklore provides some simple tools enabling us compactly to describe some truly enormous numbers. For example, the number $10^{100}$ is commonly known as a googol, and a googol ...
84
votes
4answers
7k views

If $x$, $y$, $x+y$, and $x-y$ are prime numbers, what is their sum?

Suppose that $x$, $y$, $x−y$, and $x+y$ are all positive prime numbers. What is the sum of the four numbers? Well, I just guessed some values and I got the answer. $x=5$, $y=2$, $x-y=3$, $x+y=7$. All ...
84
votes
9answers
11k views

How do I compute $a^b\,\bmod c$ by hand?

How do I efficiently compute $a^b\,\bmod c$: When $b$ is huge, for instance $5^{844325}\,\bmod 21$? When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, ...
83
votes
7answers
43k views

What is the algebraic intuition behind Vieta jumping in IMO1988 Problem 6?

Problem 6 of the 1988 International Mathematical Olympiad notoriously asked: Let $a$ and $b$ be positive integers and $k=\frac{a^2+b^2}{1+ab}$. Show that if $k$ is an integer then $k$ is a perfect ...
83
votes
4answers
3k views

How to solve these two simultaneous “divisibilities” : $n+1\mid m^2+1$ and $m+1\mid n^2+1$

Is it possible to find all integers $m>0$ and $n>0$ such that $n+1\mid m^2+1$ and $m+1\,|\,n^2+1$ ? I succeed to prove there is an infinite number of solutions, but I cannot progress anymore. ...
82
votes
6answers
9k views

Any rectangular shape on a calculator numpad when divided by 11 gives an integer. Why?

I have come across this fact a very long time ago, but I still can't tell why is this happening. Given the standard calculators numpad: 7 8 9 4 5 6 1 2 3 if you ...
81
votes
9answers
4k views

Divisibility by 7 rule, and Congruence Arithmetic Laws

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = (...
79
votes
6answers
21k views

What is special about the numbers 9801, 998001, 99980001 ..?

Just saw this post, and realized that 1/9801 = 0.00(...
76
votes
2answers
39k views

Alternative proof that $(a^2+b^2)/(ab+1)$ is a square when it's an integer

Let $a,b$ be positive integers. When $$k = \frac{a^2 + b^2}{ab+1}$$ is an integer, it is a square. Proof 1: (Ngô Bảo Châu): Rearrange to get $a^2-akb+b^2-k=0$, as a quadratic in $a$ this has two ...
73
votes
14answers
84k views

Dividing 100% by 3 without any left

In mathematics, as far as I know, you can't divide 100% by 3 without having 0,1...% left. Imagine an apple which was cloned two times, so the other 2 are completely equal in 'quality'. The totality ...
73
votes
15answers
16k views

I don't understand the homework of my little sister - do you?

She visits third class and is $8$ years old (you can imagine how ashamed I felt when I said so to her). I helped her with lots of maths stuff today already but this is very unknowable for me. Sorry it'...
72
votes
16answers
39k views

For any prime $p > 3$, why is $p^2-1$ always divisible by 24?

I know this is very basic and old hat to many, but I love this question and I am interested in seeing whether there are any proofs beyond the two I already know.
71
votes
7answers
9k views

Multiple-choice: sum of primes below $1000$

I sat an exam 2 months ago and the question paper contains the problem: Given that there are $168$ primes below $1000$. Then the sum of all primes below 1000 is (a) $11555$ (b) $76127$ (c) $...
71
votes
4answers
22k views

How to use the Extended Euclidean Algorithm manually?

I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
70
votes
7answers
5k views

Does associativity imply commutativity?

I used to think that commutativity and associativity are two distinct properties. But recently, I started thinking of something which has troubled this idea: $$(1+1)+1 = 1+ (1+1)\implies 2+1=1+2$$ ...
66
votes
5answers
7k views

Are there an infinite number of prime numbers where removing any number of digits leaves a prime?

Suppose for the purpose of this question that number $1$ is a prime number. Consider the prime number $311$. If we remove one $1$ from the number we arrive at the number $31$ which is also prime. If ...
66
votes
6answers
10k views

Why is $9$ special in testing divisiblity by $9$ by summing decimal digits? (casting out nines)

I don't know if this is a well know fact but I have observed that every number no matter how large that is equally divided by $9$, will equal $9$ if you add all the numbers it is made from until there ...
64
votes
8answers
14k views

What is $\gcd(0,0)$?

What is the greatest common divisor of $0$ and $0$? On the one hand, Wolfram Alpha says that it is $0$; on the other hand, it also claims that $100$ divides $0$, so $100$ should be a greater common ...
64
votes
2answers
7k views

Can $18$ consecutive integers be separated into two groups,such that their product is equal?

Can $18$ consecutive positive integers be separated into two groups, such that their product is equal? We cannot leave out any number and neither we can take any number more than once. My work: ...
63
votes
11answers
252k views

Modulo of a negative number

Consider the following expression: (a - b) mod N Which of the following is equivalent to the above expression? ...
63
votes
0answers
1k views

$\frac{1}{n}$ as a difference of Egyptian fractions with all denominators $<n$

Is there a good characterization of the set $S$ of positive integers $n$ such that $\frac{1}{n}$ can be represented as a difference of Egyptian fractions with all denominators $< n$? For example, $...
62
votes
4answers
4k views

Does the string of prime numbers contain all natural numbers?

Does the string of prime numbers $$2357111317\ldots$$ contain every natural number as its sub-string?
61
votes
5answers
7k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
60
votes
11answers
16k views

Why is Euclid's proof on the infinitude of primes considered a proof?

I've expressed Euclid's proof on the infinitude of primes on Mathematica: ...
59
votes
7answers
6k views

The last digit of $2^{2006}$

My 13 year old son was asked this question in a maths challenge. He correctly guessed 4 on the assumption that the answer was likely to be the last digit of $2^6$. However is there a better ...
59
votes
11answers
26k views

Proof that a Combination is an integer

From its definition a combination $\binom{n}{k}$, is the number of distinct subsets of size $k$ from a set of $n$ elements. This is clearly an integer, however I was curious as to why the expression ...
58
votes
8answers
30k views

Prove every odd integer is the difference of two squares

I know that I should use the definition of an odd integer ($2k+1$), but that's about it. Thanks in advance!
56
votes
7answers
135k views

How to find the inverse modulo m?

For example: $$7x \equiv 1 \pmod{31} $$ In this example, the modular inverse of $7$ with respect to $31$ is $9$. How can we find out that $9$? What are the steps that I need to do? Update If I have ...
55
votes
1answer
1k views

On Ramanujan's curious equality for $\sqrt{2\,(1-3^{-2})(1-7^{-2})(1-11^{-2})\cdots} $

In Ramanujan's Notebooks, Vol IV, p.20, there is the rather curious relation for primes of form $4n-1$, $$\sqrt{2\,\Big(1-\frac{1}{3^2}\Big) \Big(1-\frac{1}{7^2}\Big)\Big(1-\frac{1}{11^2}\Big)\Big(1-\...
54
votes
6answers
6k views

Prove that the sum of pythagorean triples is always even

Problem: Given $a^2 + b^2 = c^2$ show $a + b + c$ is always even My Attempt, Case by case analysis: Case 1: a is odd, b is odd. From the first equation, $odd^2 + odd^2 = c^2$ $odd + odd = c^2 \...
54
votes
4answers
2k views

Finding triplets $(a,b,c)$ such that $\sqrt{abc}\in\mathbb N$ divides $(a-1)(b-1)(c-1)$

When I was playing with numbers, I found that there are many triplets of three positive integers $(a,b,c)$ such that $\color{red}{2\le} a\le b\le c$ $\sqrt{abc}\in\mathbb N$ $\sqrt{abc}$ divides $(a-...
54
votes
1answer
670 views

Is there a “good” reason why $\left\lfloor \frac{n!}{11e}\right\rfloor$ is always even?

(A follow-up of sorts to this question.) The quantity $\left\lfloor \frac{n!}{11e}\right\rfloor$ is always even, which can be proved as follows. Using the sum for $\frac{1}{e}$, we split the ...
52
votes
5answers
18k views

Highest power of a prime $p$ dividing $N!$

How does one find the highest power of a prime $p$ that divides $N!$ and other related products? Related question: How many zeros are there at the end of $N!$? This is being done to reduce abstract ...
51
votes
6answers
10k views

There exists a power of 2 such that the last five digits are all 3's or 6's. Find the last 5 digits of this number

I just took an olympiad and I'm wondering how this problem is solved. Problem: There exists a power of 2 such that the last five digits are all 3's or 6's. Find the last 5 digits of this number. ...