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

learn more… | top users | synonyms (1)

19
votes
2answers
195 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
11k 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
4k views

Why is Euler's Totient function always even?

I want to prove why $\phi(n)$ is even for $n>3$. So far I am attempting to split this into 2 cases. Case 1: $n$ is a power of $2$. Hence $n=2^k$. So $\phi(n)=2^k-2^{k-1}$. Clearly that will ...
18
votes
5answers
24k 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
622 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
932 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
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.)
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
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
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 ...
18
votes
3answers
990 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
374 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
324 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
166 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
661 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
1answer
685 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
558 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
507 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
747 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
3answers
2k views

Find all the integral solutions to $x^6-y^6+3x^4y-3y^4x+y^3+3x^2+3x+1=0$

If $x,y\in\mathbb{Z}_{+}$, then find all the integral solutions to: $$x^6-y^6+3x^4y-3y^4x+y^3+3x^2+3x+1=0$$ I tried solving this question for an hour but still couldn't get it. I tried ...
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
4answers
738 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
799 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
940 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
464 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
601 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
4answers
497 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 ...
17
votes
2answers
731 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
473 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 ...
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
514 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
146 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 ...
16
votes
13answers
4k 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!} = ...
16
votes
6answers
15k 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.