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

learn more… | top users | synonyms (1)

16
votes
6answers
12k views

Prove that if $\gcd( a, b ) = 1$ then $\gcd( ac, b ) = \gcd( c, b ) $

I know it might be too easy for you guys here. I'm practicing some problems in the textbook, but this one really drove me crazy. From $\gcd( a, b ) = 1$, I have $ax + by = 1$, where should I go from ...
16
votes
5answers
2k views

Prove that every number ending in a $3$ has a multiple which consists only of ones.

Prove that every number ending in a $3$ has a multiple which consists only of ones. Eg. $3$ has $111$, $13$ has $111111$. Also, is their any direct way (without repetitive multiplication and ...
16
votes
2answers
1k views

To prove that $ [n/1]+ [n/2]+[n/3]+\dots +[n/n]+[\sqrt{n}]$ is even. [duplicate]

Let $n$ be a natural number. How do you prove that $$ \lfloor n/1 \rfloor+ \lfloor n/2\rfloor+ \lfloor n/3\rfloor+\dots +\lfloor n/n]+\lfloor \sqrt{n}\rfloor$$ is even? Thanks.
16
votes
6answers
1k views

Prove $a+b+c+d $ is composite

Let $a,b,c,d$ be natural numbers with $ab=cd$. Prove that $a+b+c+d$ is composite. I have my own solution for this (As posted) and i want to see if there is any other good proofs.
16
votes
5answers
812 views

Puzzle: Cumulative Sum Divisible by 10

If we sum the first $4$ positive integers, we get $4 + 3 + 2 + 1 = 10$, which I think is pretty cool. I'm interested in seeing solutions to the following puzzle: If we take the cumulative sum of the ...
16
votes
6answers
637 views

Calculate the 146th digit after the decimal point of $ \frac{1}{293} $

The question is: Calculate the 146th digit after the decimal point of $\frac{1}{293}$ 1 / 293 = 0,00341296928.., so e.g., the fifth digit is a 1. We know that 293 is a prime, probably this would ...
16
votes
2answers
133 views

For $N\in \mathbb{N}$, do there exist natural numbers $N<n_1<n_2<\cdots<n_k$ such that $\frac{1}{n_1}+\cdots+\frac{1}{n_k}=1$?

$N$ is a natural number. Is there any $k$ and some natural numbers $N<n_1<n_2<\cdots<n_k$ such that $$\frac{1}{n_1}+\frac{1}{n_2}+\cdots+\frac{1}{n_k}=1$$?
16
votes
5answers
896 views

Every integer vector in $\mathbb R^n$ with integer length is part of an orthogonal basis of $\mathbb R^n$

Suppose $\vec x$ is a (non-zero) vector with integer coordinates in $\mathbb R^n$ such that $\|\vec x\| \in \mathbb Z$. Is it true that there is an orthogonal basis of $\mathbb R^n$ containing $\vec ...
16
votes
3answers
1k views

A fun problem by Arnold using the Poincaré recurrence theorem

I came across this problem by V. I. Arnold while studying his classical mechanics book. Consider a sequence where the $n^{th}$ term is made up by considering the first digit of $2^n$, the first ...
16
votes
1answer
373 views

All elements in $\mathbb{Z}/n\mathbb{Z}$ are representable as sum of a square and a cube?

Is it true that all elements in $\mathbb{Z}/n\mathbb{Z}$ are representable as the sum of a square and a cube? Example: ($n=7$) $0 \equiv 0^2+0^3 \left( \text{mod } 7 \right)$ $1 \equiv 1^2+0^3 ...
16
votes
3answers
967 views

Finitely many Supreme Primes?

A challenge on codegolf.stackexchange is to find the highest "supreme" prime: http://codegolf.stackexchange.com/questions/35441/find-the-largest-prime-whose-length-sum-and-product-is-prime A supreme ...
16
votes
3answers
5k views

Why is there no explicit formula for the factorial?

I am somewhat new to summations and products, but I know that the sum of the first positive n integers is given by: $$\sum_{k=1}^n k = \frac{n(n+1)}{2} = \frac{n^2+n}{2}$$ However, I know that no ...
16
votes
3answers
545 views

Solving $p_1^{e_1} p_2^{e_2}…p_k^{e_k}=e_1^{p_1} e_2^{p_2}…e_k^{p_k}$

Find all positive integers $k$, positive integers $e_i$, and distinct prime numbers $p_i$ for $1\le i\le k$, such that $$p_1^{e_1} p_2^{e_2}...p_k^{e_k}=e_1^{p_1} e_2^{p_2}...e_k^{p_k}.$$ Is this ...
16
votes
2answers
419 views

Integer values of $\frac{x}{y}+\frac{y}{z}+\frac{z}{x}$?

What are the possible integer values of $$\frac{x}{y}+\frac{y}{z}+\frac{z}{x}$$ where $x$, $y$, and $z$ are positive integers? My suspicion is the the only integer values are $3$ and $5$, the former ...
16
votes
2answers
359 views

Question from Putnam '89: Primes of the form $101\ldots01$

I'm not a math major, but would like to compete in the Putnam. As suggested in other questions here, I'm working some old contest problems. I'd like some input on this attempted proof--general input ...
16
votes
1answer
1k views

Given a set of digits, what is the biggest number we can make using exponentiation - numberphile noodle quiz

The question is motivated by a question on a can of number noodles. Each item is a digit between $0$ and $9$. Clearly, if you form a string and consider it to represent a base $10$ integer, then ...
16
votes
2answers
325 views

On $a^4 + b^4 = c^4 + d^4 = e^5$.

Let $a, b, c, d, e$ be distinct positive integers such that $a^4 + b^4 = c^4 + d^4 = e^5$. Show that $ac + bd$ is a composite number.
16
votes
2answers
2k views

what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by 47?

Can any one please tell the approach or solve the question what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by $47$? I can solve remainder of $45!$ divided by $47$ using Wilson's ...
16
votes
2answers
825 views

$(x-a)(x-b)(x-c)(x-d)=ex$

We can verify that $x=125,162,343$ are the roots of equation $(x-105)(x-210)(x-315)=2584x$. My question is,Could you find five positive integers $a,b,c,d,e$, which $(x-a)(x-b)(x-c)(x-d)=ex$ has four ...
15
votes
13answers
3k views

Can the factorial function be written as a sum?

I know of the sum of the natural logarithms of the factors of n! , but would like to know if any others exist.
15
votes
4answers
2k views

Proof that one large number is larger than another large number

Let $a = (10^n - 1)^{(10^n)}$ and $b=(10^n)^{(10^n - 1)}$ Which of these numbers is greater as n gets large? I believe it is $a$ after looking at some smaller special cases, but I'm not sure how to ...
15
votes
5answers
3k views

Is it true that the Fibonacci sequence has the remainders when divided by 3 repeating?

About this Fibonacci sequence, is it true that the remainders when divided by three repeat along with the sequence like this: Fibonacci sequence: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
15
votes
14answers
2k views

Name of the highest power of 2 smaller than or equal to a given number

For a number $x$, I would like to know whether there is a common name for the number $2^n$ such as $2^n \leq x < 2^{n+1}$ (e.g. If $x = 7$, then $2^n = 4$, $n = 2$). I have some computer science ...
15
votes
6answers
463 views

can a number of the form $x^2 + 1 $ be a square number?

I have been trying to prove that $x^2 + 1 $ is not a perfect square (other than $0^2 +1^2=1^2$). I'm stuck and can't move forward. The thing I have tried so is to relate the problem to a hyperbola ...
15
votes
5answers
17k views

Is there a formula to calculate the sum of all proper divisors of a number?

I don't need to list all proper divisors, I just want to get its sum. Because for a small number, checking all proper divisors and adding them up is not a big deal. However, for a large number, this ...
15
votes
6answers
2k views

Divisibility criteria of 24. Why is this?

I am currently familiar with the method of checking if a number is divisible by $2, 3, 4, 5, 6, 8, 9, 10, 11$. While Checking for divisibility for $24$ (online). I found out that the number has to ...
15
votes
4answers
2k views

Elementary central binomial coefficient estimates

How to prove that $\quad\displaystyle\frac{4^{n}}{\sqrt{4n}}<\binom{2n}{n}<\frac{4^{n}}{\sqrt{3n+1}}\quad$ for all $n$ > 1 ? Does anyone know any better elementary estimates?
15
votes
4answers
3k views

Proving that there are infinitely many primes with remainder of 2 when divided by 3

I need to prove that there are infinitely many primes with remainder of 2 when divided by 3. I started out similarly to Euclid's classic proof of an infinite number of prime numbers: Suppose there is ...
15
votes
4answers
1k views

What's the first power of two for which the most significant digit is 7?

I was just reading an anecdote about a third-grade student who was asked by her math teacher to find a number which, when two is raised to the power of that number, produces a number that starts with ...
15
votes
5answers
2k views

Can n! be a perfect square when n is an integer greater than 1?

Can n! be a perfect square when n is an integer greater than 1?
15
votes
2answers
867 views

Puzzle: $(\Box @)+(\Box @) = (\Box\bigstar\Box$)

Some ETs follow a positional number system, with the same base as the number of fingers on their hand. The following inscription is all the evidence we have: $$(\Box @)+(\Box @) = \Box\bigstar\Box ...
15
votes
6answers
546 views

Is Pigeonhole Principle the negation of Dedekind-infinite?

From Wiki, "The Pigeonhole Principle": In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more ...
15
votes
2answers
890 views

Continued fraction for $\frac{1}{e-2}$

A couple of years ago I found the following continued fraction for $\frac1{e-2}$: $$\frac{1}{e-2} = 1+\cfrac1{2 + \cfrac2{3 + \cfrac3{4 + \cfrac4{5 + \cfrac5{6 + \cfrac6{7 + \cfrac7{\cdots}}}}}}}$$ ...
15
votes
6answers
391 views

If $(a,b,c)=1$, is there $n\in \mathbb Z$ such that $(a,b+nc)=1$?

In the book Lectures on modular forms, one finds the statement at page 8 that If $(a,b,c)=1$ then there is $n\in \mathbb Z$ such that $(a,b+nc)=1$. I know that, if $(a,b)=1$, then we can ...
15
votes
1answer
935 views

Is there a prime number between every prime and its square?

For each prime number $p$, is there always an other prime number between $p$ and $p^2$ ? I tested it for prime numbers $< 500,000,000$, but I wanted to know if there is any mathematical proof of ...
15
votes
2answers
2k views

Multiples of an irrational number forming a dense subset

Say you picked your favorite irrational number $q$ and looking at $S = \{nq: n\in \mathbb{Z} \}$ in $\mathbb{R}$, you chopped off everything but the decimal of $nq$, leaving you with a number in ...
15
votes
2answers
387 views

Solution in integers to $2^n+n=3^m$

How to find all positive integers $m,n$ such that $2^n+n=3^m$ ? We have by inspection $(m,n)=(0,0)$ and $(1,1)$ And there are no more for m and n both less then $100$.
15
votes
3answers
657 views

New identity for Euler's Totient Function?

A few weeks ago I discovered and proved a simple identity for Euler's totient function. I figured that someone would have already discovered it, but I haven't been able to find it anywhere. So I was ...
15
votes
4answers
579 views

Need help understanding Erdős' proof about divergence of $\sum\frac1p$

I'm looking at proofs from Proofs from the Book (Martin Aigner, Günter M. Ziegler). The proof I'm having trouble is the sixth proof of the infinitude of the primes they give (on page 5; although I'll ...
15
votes
2answers
218 views

Proving that $\frac{n!-1}{2n+7}$ is not an integer when $n>8$

How can I prove that If $n$ is a positive integer such that $$n>8$$ then $$\frac{n!-1}{2n+7}$$ is never an integer? Some of the first things that came to my mind is that $n!-1$ is not divisible by ...
15
votes
1answer
273 views

$a^b+2$ or $a^b-2$ is in set

Let $A$ be an infinite set of positive integers. For any two $a,b\in A$, $a\neq b$, at least one of the numbers $a^b+2$ and $a^b-2$ are also in $A$. Must $A$ contain a composite number?
15
votes
4answers
438 views

sum of cubes of two rationals

How to find two rational numbers $x,y$ such that $$x^3+y^3=6$$ I know that $x=17/21,y=37/21$ is a solution but I am interested in a method how is achieved and does exists other solutions
15
votes
3answers
406 views

Is computing distance a lesser capability than computing square roots?

Let $F$ be a field. Consider the following three abilities: (SQRT) Given $a\in F$, find $x\in F$ such that $a = x^2$ (when such $x$ exists). (NORM) Given $a,b\in F$, find $x\in F$ such that ...
15
votes
1answer
230 views

How prove $\sqrt{r^2+c^2}$ is irrational

Question: Let $a,b,c$ are integer numbers,and $r$ real numbers, and $$ar^2+br+c=0,ac\neq 0$$ show that $$\sqrt{r^2+c^2}$$ is irrational. My idea: Note that, ...
15
votes
1answer
364 views

Find the terms of the sequence $a_{n+1}=1+n/a_n$ that are natural numbers

Let's consider the sequence $(a_n)_{n\in\mathbb{N}}$, defined by the following recurrence relation: $$ a_{n+1} = \begin{cases} 1 + \frac{n}{a_{n}}\quad&n\gt0\\ 1&n=0 \end{cases} $$ Find all ...
15
votes
4answers
306 views

Find $x,y,z \in \mathbb Q$ such that $x + \frac 1y, y + \frac 1z, z+ \frac 1x \in \mathbb Z$

Find $x,y,z \in \mathbb Q$ such that: $$x + \frac 1y, y + \frac 1z, z+ \frac 1x \in \mathbb Z$$ Here is my thinking: $$x + \frac 1y, y + \frac 1z, z+ \frac 1x \in \mathbb Z\\ \implies \left ( x ...
15
votes
2answers
610 views

Formula for number of solutions to $x^4+y^4=1$, from Ireland and Rosen #8.18.

There is a sequence of three exercise in Ireland and Rosen's Introduction to Modern Number Theory, Chapter 8, page 106. I can do the first two, but can't finish the third. I can include the proofs to ...
15
votes
1answer
1k views

Would proof of Legendre's conjecture also prove Riemann's hypothesis?

Legendre's conjecture is that there exists a prime number between $n^2$ and $(n+1)^2$. This has been shown to be very likely using computers, but this is merely a heuristic. I have read that if this ...
15
votes
3answers
630 views

Finding when $(a-n)(b-n)|(ab-n)$

Given $n$ and $k$, find the number of pairs of integers $(a, b)$ which satisfy the conditions $n < a < k, n < b < k$ and $(ab-n)$ is divisible by $(a-n)(b-n)$. Given: $0 ≤ n ≤ 100000, \ n ...
15
votes
2answers
452 views

Euler's Totient function $\forall n\ge3$, if $(\frac{\varphi(n)}{2}+1)\ \mid\ n\ $ then $\frac{\varphi(n)}{2}+1$ is prime

While I was studying Euler's Totient function, $\varphi(n)$, I stumbled upon the marvelous book "Index to Mathematical Problems, 1980-1984" By Stanley Rabinowitz. In this page of the book (link to ...