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

learn more… | top users | synonyms (1)

16
votes
2answers
351 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
324 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
809 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
8answers
3k views

Prove that none of $\{11, 111, 1111,\dots \}$ is the perfect square of an integer

Please help me with solving this : prove that none of $\{11, 111, 1111 \ldots \}$ is the square of any $x\in\mathbb{Z}$ (that is, there is no $x\in\mathbb{Z}$ such that $x^2\in\{11, 111, 1111, ...
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
462 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
6answers
541 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
884 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
923 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
383 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
643 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
569 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
217 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
434 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
405 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
363 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
304 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
601 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
423 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 ...
15
votes
1answer
159 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
316 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
548 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
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
705 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
6answers
2k views

Prove a number is composite

How can I prove that $$n^4 + 4$$ is composite for all $n > 5$? This problem looked very simple, but I took 6 hours and ended up with nothing :(. I broke it into cases base on quotient remainder ...
14
votes
2answers
929 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
782 views

Why is the zero polynomial not assigned a degree?

Yesterday, I read in my textbook, We assign degree to every polynomial and even a non-zero constant is assigned a degree $0$ but $0$ itself is not assigned a degree. Why is that? Why we don't ...
14
votes
3answers
2k 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
453 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
280 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
859 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
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?
14
votes
4answers
567 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
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
885 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 ...