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

learn more… | top users | synonyms (1)

254
votes
14answers
30k 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 ...
176
votes
2answers
14k views

Proving you *can't* make $2011$ out of $1,2,3,4$: nice twist on the usual

An undergraduate was telling me about a puzzle he'd found: the idea was to make $2011$ out of the numbers $1, 2, 3, 4, \ldots, n$ with the following rules/constraints: the numbers must stay in order, ...
175
votes
3answers
7k 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=(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}}}) ...
174
votes
5answers
7k 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 ...
139
votes
19answers
10k views

Mental Calculations

This is the famous picture "Mental Arithmetic. In the Public School of S. Rachinsky." by the Russian artist Nikolay Bogdanov-Belsky. The problem presented on a blackboard requires computing the ...
136
votes
6answers
24k 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 ...
128
votes
9answers
5k 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 ...
97
votes
11answers
6k views

Is there a domain “larger” than (i.e., a supserset of) the complex number domain?

I've been teaching my 10yo son some (for me, anyway) pretty advanced mathematics recently and he stumped me with a question. The background is this. In the domain of natural numbers, addition and ...
81
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. ...
74
votes
11answers
13k 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 ...
74
votes
11answers
17k 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 should be even because it is in between -1 and +1 (i.e in between 2 odd numbers). What is the real ...
73
votes
15answers
12k 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 ...
72
votes
5answers
12k views

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

Just saw this post, and realized that 1/9801 = ...
70
votes
2answers
3k 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 ...
66
votes
5answers
10k 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$$
65
votes
14answers
34k 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 ...
65
votes
4answers
5k views

$x$, $y$, $x+y$ and $x-y$ are prime numbers. What is their sum?

Here is the question: The $x$, $y$, $x−y$ and $x+y$ are all positive prime integers. What is the sum of all the four integers? Well, I just put some values and I got the answer. $x=5$, $y=2$, ...
65
votes
11answers
7k views

Why 1 is not considered to be a prime number?

Why $1$ is not considered to be a prime number? Or why definition of prime numbers is given for integers greater than $1$?
60
votes
13answers
13k 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
5answers
8k views

Do we have negative prime numbers?

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

What makes $9$ special?

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 ...
58
votes
2answers
6k 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: ...
54
votes
4answers
3k 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?
52
votes
16answers
16k 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.
52
votes
8answers
13k 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!
26
votes
3answers
856 views

Intuition on fundamental theorem of arithmetic

I'm sorry ahead if time if this is overly trivial for this site. Currently in school, much of what I enjoy is number theory - based. Currently, I lean pretty heavily on the FTA for a good deal of my ...
18
votes
10answers
10k views

What's the proof that the Euler totient function is multiplicative?

That is, why is $\varphi (A\cdot B)=\varphi (A)\cdot \varphi (B)$, if A and B are coprime? It's not just a technical trouble—I can't see why this should be, intuitively: I bellyfeel that its ...
8
votes
4answers
596 views

How to obtain all the rational numbers without repetitions?

Some days ago I've seen Cantor's diagonal argument, and it presented a table similar to the following one: $$\begin{matrix} ...
7
votes
2answers
119 views

how to prove : $(p-1)!\equiv p-1 \pmod {p(p-1)})$

how to prove : $$(p-1)!\equiv p-1 \pmod {p(p-1)})$$ my efford : we have: $(p-1)!\equiv-1\equiv p-1\pmod p$ but $(p-1)!\equiv 0\pmod {p-1}$ if $(p-1)!\equiv p-1\pmod {p-1}$ then we had $(p,p-1)=1$ ...
6
votes
5answers
2k views

Show $\sum\limits_{d|n}\phi(d) = n$. [duplicate]

Show $\sum\limits_{d|n}\phi(d) = n$. Example : $\sum\limits_{d|4}\phi(d) = \phi(1) + \phi(2) + \phi(4) = 1 + 1 + 2 = 4$ I was told this has a simple proof. Problem is, I can not think of a way to ...
6
votes
3answers
2k views

How does summation formula work with floor function?

Prove that if a and b are relatively prime, then $$\sum_{n=1}^{a-1} \left\lfloor \frac{nb}{a}\right\rfloor = \frac{(a - 1)(b - 1)}{2}$$ My attempt was: We have: $$\sum_{i=1}^{n-1} i = \frac{n(n ...
6
votes
2answers
122 views

Count with only certain digits allowed - And feel a fractal

I have a friend ~200 years old mathematician who has forgotten some digits and now he counts things in very strange manner: when he is going to count the $n$-th thing and $n$ contains a digit he ...
5
votes
1answer
58 views

Why is the Fundamental Theorem of Arithmetic so important?

I've recently read about the Fundamental Theorem of Arithmetic and I think that I have just about understood the proof. What I found quite interesting at first was the "Fundamental" part in the name. ...
3
votes
2answers
52 views

Finding the sum of all products of pairs of distinct primitive roots mod 83

I'm currently studying Number Theory and I've stumbled upon a question where I need to: Find the sum of all products of pairs of distinct primitive roots mod 83. Solving attempt: I've tried to find ...
3
votes
1answer
27 views

Fractions of powers of primes.

I'm wondering whether the following statement is true: Let $p$ and $q$ be two prime numbers (or more generally let $p$ and $q\neq 0$ be integers with $\gcd(p,q)=1$). Then for all $\varepsilon >0$ ...
2
votes
3answers
107 views

Integer solutions to $x^2-xy+y^2=1$

What are the integer solutions to $x^2-xy+y^2=1$? (I found the solution below while working on another problem, so I thought I'll add it to the knowledge base here.)
2
votes
1answer
40 views

prove C is a proper subset of ℕ. Then prove ℕ is infinite.

Please, can you help me to do this? Let $C =\{n + n \;|\; n\in \mathbb{N} \}$, and define $f:\mathbb{N}\to C$ by $f(n) = n + n$. First prove $C$ is a proper subset of $\mathbb{N}$. Then prove ...
2
votes
1answer
37 views

Looking for a simpler solution about quadratic congruence

Here is the Problem: 1)Suppose $p$ is a prime. prove that for any integer $k$, there exist integers $x$ and $y$ such that $x^2+y^2 \equiv k\ \pmod p$. 2)Are there infinitely many composite ...
2
votes
1answer
58 views

Find all values of N that satisfy ϕ(N) = x for any given x value

How would I determine all values of n in ϕ(n) = x for any value of x where ϕ is Euler's totient function? (and -1 if x is not a totient). Is there a simple formula for this? Or is this a lot more ...
1
vote
2answers
10 views

Can the state of a system after applying the operation “absolute value” be got back using elementary operations or transformations?

Take the operation or transformation "addition". You can get back the original state of the system by doing the opposite operation, i.e., "subtraction". But, if the operation is "absolute value", you ...
1
vote
0answers
26 views

For how many n's less than 100 do we have $s(n)=s(n+i)$

We define $s(n)$ as $LCM(least\ common\ multiplier)$ of numbers $1\ through\ n$. For how many $n's $ less than $100$ do we have: $s(n)=s(n+i),(i$ is a positive integer less than $10)??$ I have ...
0
votes
1answer
39 views

A problem based on number theory?

If 'p' is a prime greater than 3, then show that 2p + 1 and 4p + 1 cannot be primes simultaneously. Do I have to use Fermat's Little Theorem to solve this?
0
votes
3answers
56 views

Alternative Proof: if $n$ is an integer, prove that $\frac{n ( n^4 - 1)}{5}$ is an integer

I have proven this by the induction method but would like to know if it can be proven using an alternative method.
0
votes
2answers
33 views

Can you show that $3n+1$ is not divisible by $5$ using congruences?

I'm trying to prove that the difference of two consecutive cubes is never divisible by $5$, and I got to a point where I would have to prove that $3n+1$ is not divisible by $5$, where n is an integer. ...
0
votes
1answer
27 views

Find how many solutions the congruence $x^2 \equiv 121 \mod 1800$ has

I want to find how many solutions the congruence $x^2 \equiv 121 \mod 1800$ has. What is the method to find it without calculating all the solutions? I can't use euler criterion here because 1800 ...
0
votes
1answer
26 views

Elementary number theory with some arithmetic progression.

Let A={n∈N┤n is the sum of seven consecutive integers}. B={n∈N┤|n is the sum of eight consecutive integers}. C={n∈N┤|n is the sum of nine consecutive integers}. Find A∩B∩C. I tried ...
0
votes
1answer
56 views

Proof, that $a \equiv 1 \pmod{p}$

Let $n \in \mathbb{N}^{+} \smallsetminus \{{1}\}$ and $p = min\{p \in \mathbb{P} : p \mid n\}$. Also, let $a \in \mathbb{Z}$ and $a^n \equiv 1 \pmod{n}$ I need to proof, that $a \equiv 1 \pmod{p}$. ...
-1
votes
0answers
13 views

Number of ways to write $n \in \Bbb N$ as a sum of $k$ positive integers? [on hold]

For example: The number of ways to write $6$ as a sum of $6$ positive integers is $1$ which is $1+1+1+1+1+1$. And the number of ways to write $10$ as a sum of $2$ positive integers is $5$. I need the ...
-2
votes
0answers
40 views

Prime number theory. [on hold]

If $a$ is coprime to $b$ and $y$ and $b$ are both coprime to $x$; then Prove that $ax+by$ is a coprime to $ab$.
-61
votes
9answers
4k views

Unique Representation and The Fundamental Theorem of Arithmetic

While reading this thread Why 1 is not considered to be a prime number?, I recalled that The Fundamental Theorem of Arithmetic (FTA) which says that every positive integer greater than $1$ can get ...