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

learn more… | top users | synonyms (1)

19
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? (But is it possible, to prove without Bertrand's postulate. Because bertrands postulate is quite a strong result.)
19
votes
5answers
506 views

Is $11^2+12^2+13^2+14^2+15^2+16^2=1111$ special?

Is this pure coincidence or is this a special case of some well-known number-theoretic result? If the latter is true, is there some notable generalization? EDIT: Thanks to the interesting answers ...
19
votes
4answers
3k 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, ...
19
votes
2answers
3k 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 ...
19
votes
2answers
197 views

For all $n$ there exists $x$ such that $\varphi(x)<\varphi(x+1)<\ldots<\varphi(x+n)$

Let $\varphi$ be the Euler's function, i.e. $\varphi(n)$ stands for the number of integers $m \in \{1,\ldots,n\}$ such that $\text{gcd}(m,n)=1$. Let $n\ge 2$ be a positive integer. Show that there ...
18
votes
6answers
3k views

Is there a way to write an infinite set that contains only irrational numbers without integer multiples?

Is there a way to write an infinite set that contains only irrational numbers without integer multiples? The infinite set must not contain integer multiples of any other members of that set. For ...
18
votes
9answers
4k 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, ...
18
votes
7answers
5k views

Prime dividing the binomial coefficients

It is quite easy to show that for every prime $p$ and $0<i<p$ we have that $p$ divides the binomial coefficient $\large p\choose i$; one simply notes that in $\large \frac{p!}{i!(p-i)!}$ the ...
18
votes
8answers
12k views

What rational numbers have rational square roots?

All rational numbers have the fraction form $$\frac a b,$$ where a and b are integers($b\neq0$). My question is: for what $a$ and $b$ does the fraction have rational square root? The simple answer ...
18
votes
5answers
25k 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 ...
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 ...
18
votes
5answers
624 views

How to prove that $\frac{(mn)!}{m!(n!)^m}$ is an integer?

$\forall m,n\in\mathbb Z$ , $m\ge1$ and $n\ge1$ how to prove that $$\frac{(mn)!}{m!(n!)^m}$$ is an integer? Thanks in advance.
18
votes
3answers
941 views

Prove that the number 14641 is the fourth power of an integer in any base greater than 6?

Prove that the number $14641$ is the fourth power of an integer in any base greater than $6$? I understand how to work it out, because I think you do $$14641\ (\text{base }a > 6) = ...
18
votes
3answers
1k views

Proving there are an infinite number of pairs of positive integers $(m,n)$ such that $\frac{m+1}{n}+\frac{n+1}{m}$ is a positive integer

The question is: Show that there are an infinite number of pairs $(m,n): m, n \in \mathbb{Z}^{+}$, such that: $$\frac{m+1}{n}+\frac{n+1}{m} \in \mathbb{Z}^{+}$$ I started off approaching this ...
18
votes
5answers
995 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 ...
18
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 ...
18
votes
3answers
2k views

Infer number of terms in sum, given the value of the sum

In preparation for a math contest my little brother's teacher gave him a nice little book full of interesting little math exercises. And whenever my brother got stuck, he asks me for help and we ...
18
votes
4answers
501 views

Do there exist infinitely many pairs of primes $(p,q)$ such that $pq$ divides $2^{p-1}+2^{q-1}-2$?

A mathematician friend gave me this question (partly as a joke) a few months ago and it has puzzled me for a long time:- Do there exist infinitely many pairs of primes $(p,q)$ such that ...
18
votes
3answers
997 views

Proof by induction that $n^3 + (n + 1)^3 + (n + 2)^3$ is a multiple of $9$. Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
18
votes
2answers
379 views

Without using Heegner-Stark-Baker, $\mathbb{Q}(\sqrt{-11})$ has class number $1$.

Prove that $\mathbb{Q}(\sqrt{-11})$ is of class number $1$. I have found that the ideal $(2)$ of the integer ring $\mathbb{Z}[(1 + \sqrt{-11})/2]$ of $\mathbb{Q}(\sqrt{-11})$ is a prime ideal. ...
18
votes
1answer
326 views

Some trigo identities

I aacidently found the following: $$\sin\frac{2\pi}{7}+\sin\frac{4\pi}{7}-\sin\frac{6\pi}{7}=\frac{\sqrt{7}}{2}$$ ...
18
votes
3answers
167 views

Is the numerator of $\sum_{k=0}^n \frac{(-1)^k}{2k+1}\binom{n}{k}$ a power of $2$?

I stumbled on something numerically, and was just starting to work on it, but it seemed fun enough to share. Let $$f(n)=\sum_{k=0}^{n} \frac{(-1)^{k}}{2k+1}\binom{n}{k}$$ It appears, from the ...
18
votes
1answer
663 views

Primes of the form $x^2 +ny^2$ where swapping $x$ and $y$ still gives a prime

I am studying primes of the form $x^2+ny^2$, and i was wondering if there are any known results about the primes of this form such that when you swap $x$ and $y$ you also get a prime. ie for ...
18
votes
2answers
527 views

Does this system of simultaneous Pell-like equations have any non-trivial positive integer solutions?

Let $a,b,c$ be positive integers satisfying \begin{align} 2a^2-1 &= b^2, \\ 2a^2+1 &= 3c^2. \end{align} The trivial solution is $(a,b,c)=(1,1,1)$. Are there others?
18
votes
1answer
686 views

Did Leonardo of Pisa prove $n=4$ case of FLT?

Reputable on-line sources agree that Leonard 'Fibonacci' proved the nonexistence of positive-integer solutions to $c^4 - b^4 = a^2$ . Yet my change to Wikipedia to reflect this was reverted. I hope ...
18
votes
2answers
570 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 ...
18
votes
2answers
494 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 ...
18
votes
2answers
508 views

Do there exist two primes $p<q$ such that $p^n-1\mid q^n-1$ for infinitely many $n$?

We can prove that there is no integer $n>1$ such that $2^n-1\mid 3^n-1$. This leads to the following question: Is it true that for every pair of primes $p<q$ there are only finitely many ...
18
votes
2answers
390 views

Are there $a,b>1$ with $a^4\equiv 1 \pmod{b^2}$ and $b^4\equiv1 \pmod{a^2}$?

Are there solutions in integers $a,b>1$ to the following simultaneous congruences? $$ a^4\equiv 1 \pmod{b^2} \quad \mathrm{and} \quad b^4\equiv1 \pmod{a^2} $$ A brute-force search didn't turn up ...
18
votes
0answers
753 views

Are there unique solutions for $n=\sum_{j=1}^{g(k)} a_j^k$?

Edward Waring, asks whether for every natural number $n$ there exists an associated positive integer s such that every natural number is the sum of at most $s$ $k$th powers of natural numbers ...
17
votes
6answers
6k views

Can you complete the expression $2 \underline{ }\, \underline{ }\, \underline{ } \,\underline{ } 5 = 2015$?

Can you complete the expression $2 \underline{ } \, \underline{ }\, \underline{ } \, \underline{ } 5 = 2015$ and make it correct by replacing two underscores with a selection of the ...
17
votes
6answers
2k views

Visual explanation of the following statement:

Can somebody fill me in on a visual explanation for the following: If there exist integers $x, y$ such that $x^2 + y^2 = c$, then there also exist integers $w, z$ such that $w^2 + z^2 = 2c$ I know ...
17
votes
3answers
4k views

Largest prime number with all digits different

What is the largest prime with distinct digits? (It is certainly less than ten digits long.Can you explain it why?
17
votes
5answers
1k views

Intervals that are free of primes

How can I prove that exists intervals as large as I want that are free of primes? I mean, $\forall \ k \in \mathbb{N}, \exists \ k$ consecutive positive integers none of which is a prime.
17
votes
6answers
2k views

Is that true that all the prime numbers are of the form $6m \pm 1$?

Is that true that all the prime numbers are of the form $6m \pm 1$ ? If so, can you please provide an example? Thanks in advance.
17
votes
4answers
743 views

Why can't $p^p-(p-1)^{p-1}=n^2$ be a square?

Let $p$ be a prime number. Show that $p^p-(p-1)^{p-1}$ can't be a square. In other words, there is no $n\in\mathbb{N}^{+}$ such that $$p^p-(p-1)^{p-1}=n^2.$$
17
votes
2answers
801 views

Large integer help

The integer $5685858885855807765856785858569666876865656567858576786786785^{22}$ has 6436343 divisors. Using only a scientific calculator, find a way to show it has exactly 5 prime divisors.
17
votes
6answers
648 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 ...
17
votes
2answers
941 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}}}}}}}$$ ...
17
votes
3answers
377 views

Is it possible that $(x+2)(x+1)x=3(y+2)(y+1)y$ for positive integers $x$ and $y$?

Let $x$ and $y$ be positive integers. Is it possible that $(x+2)(x+1)x=3(y+2)(y+1)y$? I ran a program for $1\le{x,y}\le1\text{ }000\text{ }000$ and found no solution, so I believe there are none.
17
votes
4answers
466 views

How many different numbers can be written if each used digit symbol is used at least 2 times?

How many different numbers can be written if each used digit symbol is used at least 2 times ? I would like to find the function $P(n,d)$: $P(n,d)$ where $n$ is base, $d$ is digit; Some examples: ...
17
votes
3answers
606 views

Improvement IMO 1988 $f(f(n))=n+1987$

The following problem was given at IMO 1987. Prove that there is no function f from the set of non-negative integers into itself such that $f(f(n)) = n + 1987$ for every $n$. So I tried to ...
17
votes
2answers
733 views

Multiplication tables with all entries distinct

Let positive integers $\alpha$ and $\beta$ be given. It is easy to find sets $A$ and $B$ of positive integers such that: $|A|=\alpha$ and $|B|=\beta$ The set $P = \{ab : a\in A, b\in B\}$ contains ...
17
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 ...
17
votes
1answer
2k 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 ...
17
votes
2answers
517 views

Is there an automated way to prove really boring elementary number theoretic results?

Motivation: I'm writing a proof, and within it, I need to prove: Conjecture: Let $p$ be an odd prime (i.e. $p \neq 2$). Let $c \geq 2$, $d \geq 1$ and $r \geq 1$. If $p^r$ divides $cd$, then ...
17
votes
2answers
149 views

If two integer triples have the same sum of 6th powers, then their sums of squares agree $\bmod 9$

Given $$a^6 + b^6 + c^6 = x^6 + y^6 + z^6$$ prove that $$a^2 + b^2 + c^2 - x^2 - y^2 - z^2 \equiv 0 \bmod{9}$$ I was thinking of using $n^6 \pmod{27}$ and showing both sides have the same pattern ...
17
votes
0answers
413 views

A question about the divisibility of sum of 2 consecutive primes.

Well as I was curious about the sum of $2$ consecutive primes, after proving that the sum for the odd primes always has at least 3 prime divisors, I came up with this question: Find the least ...
16
votes
13answers
5k 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.
16
votes
5answers
1k 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!} = ...