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

learn more… | top users | synonyms (1)

15
votes
2answers
121 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$$?
15
votes
2answers
863 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
388 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
886 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
379 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
4k 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 ...
15
votes
3answers
622 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
553 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
3answers
544 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 ...
15
votes
2answers
216 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
266 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
424 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
1answer
229 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
362 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
299 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
586 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
3answers
629 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
311 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.
15
votes
1answer
154 views

How to sum this infinite series

How to sum this series: $$\frac{1}{1}+\frac{1}{11}+\frac{1}{111}+\frac{1}{1111}+\cdots$$ My attempt: Multiply and divide the series by $9$ ...
15
votes
1answer
313 views

When is $(x^n-1)/(x-1)$ a prime number?

Let $x > 1$ and let $n$ be a prime. I'm wondering if a characterization of this is known. That is, what are sufficient and necessary conditions for $$ \dfrac{x^n-1}{x-1} = 1 + x + x^2 + \cdots + ...
15
votes
1answer
546 views

Prove that the product of some numbers between perfect squares is $2k^2$

Here's a question I've recently come up with: Prove that for every natural $x$, we can find arbitrary number of integers in the interval $[x^2,(x+1)^2]$ so that their product is in the form of ...
14
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.
14
votes
2answers
1k views

Show that these two numbers have the same number of digits

I want to show that for $n>0$, $2^n$ and $2^n + 1$ have the same number of digits. What I did was I found that the formula for the number of digits of a number $x$ is $\left ...
14
votes
7answers
702 views

$n^5-n$ is divisible by $10$?

I was trying to prove this, and I realized that this is essentially a statement that $n^5$ has the same last digit as $n$, and to prove this it is sufficient to calculate $n^5$ for $0-9$ and see that ...
14
votes
2answers
907 views

how to prove $437\,$ divides $18!+1$? (NBHM 2012)

I was solving some problems and I came across this problem. I didn't understand how to approach this problem. Can we solve this with out actually calculating $18!\,\,?$
14
votes
3answers
1k views

Any two positive integers are co-prime if their sum is a prime number [duplicate]

Any two positive integers are co-prime if their sum is a prime number Is this a trivial thing to say? I have a proof, but I don't want to bore anyone if it's just a trivial matter-of-fact thing about ...
14
votes
5answers
444 views

Alternate proof that for every natural number $n,\ \left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$ is divisible by $3$

Original Problem: Prove that for every natural number $n$,$$\left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$$ is divisible by $3$. I found the problem in the book Winning ...
14
votes
3answers
276 views

Showing that $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$

For any odd positive integer $k\geq1$, the sum $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$. I used induction principle for the solution but cannot prove it. I took $P(k) = ...
14
votes
2answers
845 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 ...
14
votes
4answers
527 views

Why do repunit primes have only a prime number of consecutive $1$s?

Repunit primes are primes of the form $\frac{10^n - 1}{9} = 1111\dots11 \space (n-1 \space ones)$. Each repunit prime is denoted by $R_i$, where $i$ is the number of consecutive $1$s it has. So far, ...
14
votes
4answers
1k 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?
14
votes
4answers
2k 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, ...
14
votes
2answers
826 views

Evidence against Goldbach's Conjecture?

It recently occurred to me that, unless I'm much mistaken, Goldbach's conjecture can easily be seen to be equivalent to a seemingly more general statement: Every number $n$ divisible by any ...
14
votes
2answers
377 views

$x^3+y^4=7$ has no integer solutions

I am trying to prove that $x^3+y^4=7$ has no integer solutions, but i have no idea how to start, please helps. I have tried to consider mod 7 to restrict the number of possible $x^3$ because $x^3 ...
14
votes
4answers
724 views

“If $1/a + 1/b = 1 /c$ where $a, b, c$ are positive integers with no common factor, $(a + b)$ is the square of an integer”

If $1/a + 1/b = 1 /c$ where $a, b, c$ are positive integers with no common factor, $(a + b)$ is the square of an integer. I found this question in RMO 1992 paper ! Can anyone help me to prove ...
14
votes
1answer
429 views

German sofa primes: Can both $q$ and $\frac{q^3+1}{2}$ be prime?

Is there an odd prime integer $\displaystyle q$ such that $\displaystyle p= \frac{q^3+1}{2}$ is also prime? A quick search did not find any, nor a pattern in the prime factorization of p. This ...
14
votes
3answers
977 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 ...
14
votes
2answers
246 views

Prove that $\left (\frac{a^2 + b^2 +c^2}{a+b+c} \right) ^ {(a+b+c)} > a^a b^b c^c$

Prove that $\left (\dfrac{a^2 + b^2 +c^2}{a+b+c} \right) ^ {(a+b+c)} > a^a b^b c^c$ if $a$, $b$ and $c$ are distinct natural numbers. Is it possible using induction?
14
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 ...
14
votes
1answer
250 views

Prime pair points slope approaches 1

Take the list of primes, $$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, \ldots$$ and create ordered $(x,y)$ pairs by grouping in sequence, $$(2, 3), (5, 7), (11, 13), ...
14
votes
3answers
401 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 ...
14
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 ...
14
votes
2answers
1k views

Asking 2011 Putnam B6

I wish to ask today's Putnam problem B6: Suppose $p$ is an odd prime. Prove that for $n\in \{0,1,2...p-1\}$, at least $\frac{p+1}{2}$ number of $\sum^{p-1}_{k=0} k! n^{k}$ is not divisble by $p$. ...
14
votes
2answers
360 views

A question about integers.

Let $a,b,c$ be positive integer,and $\cfrac{a}{b}+\cfrac{b}{c}+\cfrac{c}{a}$ and $\cfrac{b}{a}+\cfrac{c}{b}+\cfrac{a}{c}$ are integers, how to show $a=b=c$?
13
votes
7answers
3k views
13
votes
4answers
739 views

Prove that e is irrational

Prove that e is an irrational number. Recall that e $=\displaystyle\sum_{n=0}^\infty\frac{1}{n!},\,\,$ and assume $\mathrm{e}$ is rational. Then $$\sum\limits_{k=0}^\infty \frac{1}{k!} = ...
13
votes
3answers
941 views

Numbers are too large to show $65^{64}+64^{65}$ is not a prime

I tried to find cycles of powers, but they are too big. Also $65^{n} \equiv 1(\text{mod}64)$, so I dont know how to use that.
13
votes
6answers
662 views

Show that $\frac{(3^{77}-1)}{2}$ is odd and composite

The question given to me is: Show that $\large\frac{(3^{77}-1)}{2}$ is odd and composite. We can show that $\forall n\in\mathbb{N}$: $$3^{n}\equiv\left\{ \begin{array}{l l} 1 & \quad ...
13
votes
9answers
3k views

How to prove $n^5 - n$ is divisible by 30 without reduction

How can I prove that prove $n^5 - n$ is divisible by 30? I took $n^5 - n$ and got $n(n-1)(n+1)(n^2+1)$ Now, $n(n-1)(n+1)$ is divisible by 6. Next I need to show that $n(n-1)(n+1)(n^2+1)$ is ...
13
votes
3answers
546 views

How can I calculate $\sin\left(10^{10^{100}} - 10\right)^\circ$?

How can I calculate the sine of a googolplex minus 10 degrees?