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

learn more… | top users | synonyms

13
votes
8answers
850 views

Approximation of $e$ using $\pi$ and $\phi$?

$$e \approx \frac{4 \phi +3 \pi-5}{4}$$ where $~\phi~$ is a Golden ratio . Is it possible to construct better approximation of $e$ using $\pi$ , $\phi$ and integers ?
13
votes
3answers
933 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
652 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
5answers
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.
13
votes
3answers
524 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?
13
votes
6answers
1k views

Is there any book/resource which explain the general idea of the proof of Fermat's last theorem?

I look for a book/resource which display the general idea of the proof of Fermat last theorem in a simple manner for the public. I mean, books which is not for mathematicians but for the general ...
13
votes
5answers
3k views

If $n$ is composite, then $n$ divides $(n-1)!$.

I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. ...
13
votes
6answers
460 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 ...
13
votes
3answers
1k views

Infinity Hotel problem

Q. Welcome to the infinity hotel has an infinite number of rooms $1,2,3,4,...$ The manager notices all of the rooms have the lights on. He flips the switch every other one. (Rooms $2, 4, 6, …$) Then ...
13
votes
1answer
816 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 ...
13
votes
2answers
264 views

Can my MSE reputation be any positive integer?

As far as I know there are five kinds of vote $+2$ for an edit $-2$ for a downvote $+10$ for an answer $+15$ for an accepted answer $+5$ for a question Suppose that this is true. Can a MSE ...
13
votes
2answers
651 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 ...
13
votes
4answers
170 views

Proving $1+2^n+3^n+4^n$ is divisible by $10$

How can I prove $$1+2^n+3^n+4^n$$ is divisible by $10$ if $$n\neq 0,4,8,12,16.....$$
13
votes
2answers
2k 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 ...
13
votes
5answers
1k views

product of six consecutive integers being a perfect square

A 1939 paper of Erdos (Note on Products of Consecutive Integers, J. London Math. Soc. 14 (1939), 194–198) shows that a product of consecutive positive integers cannot be a perfect square. He ...
13
votes
2answers
149 views

Identity of a Mathematician Mentioned in Euler

I and several others are in the process of translating one of Euler's papers from Latin to English, in particular the one that the Euler Archive lists as E36. In it Euler proves the Chinese Remainder ...
13
votes
1answer
2k views

Prime with digits reversed is prime?

Well, just another idea came up into my mind and i have no idea how to solve it :D Is there infinitely many prime numbers, which are not repunits and their inverse is also prime? (For example, inverse ...
13
votes
2answers
301 views

When is $(p - 1)! + 1$ a power of $p$?

A friend asked me this question: If $p$ is a prime, prove that $(p - 1)! + 1$ is a power of $p$ if and only if $p = 2, 3$ or $5$. Clearly one direction is obvious, namely that $p=2,3,5$ implies ...
13
votes
3answers
483 views

Proof that $(3^n - 2^n) / n$ is not an integer, $n \geq 2$

Trying to prove that $(3^n - 2^n)/n$ is not an integer for $n\geq 2$. Was trying something along the lines of induction with: $3^{n+1} - 2^{n+1} = 2(3^n - 2^n) + 3^n \equiv 0 \mod (n+1)$ But that ...
13
votes
5answers
3k views

Fermat's Last Theorem near misses?

I've recently seen a video of Numberphille channel on Youtube about Fermat's Last Theorem. It talks about how there is a given "solution" for the Fermat's Last Theorem for $n>2$ in the animated ...
13
votes
2answers
433 views

Do 3 consecutive primes always form a triangle?

Suppose that $a$, $b$, and $c$ are any three consecutive primes other than the triple $2$, $3$, and $5$. Do they satisfy the triangle inequalities: $a + b > c$; $b + c > a$; $c + a > b$? ...
13
votes
4answers
369 views

Proof of Irrationality of e using Diophantine Equations

I was trying to prove that e is irrational without using the typical series expansion, so starting off $e = a/b $ Take the natural log so $1 = \ln(a/b)$ Then $1 = \ln(a)-\ln(b)$ So unless I did ...
13
votes
2answers
454 views

A puzzle with powers and tetration mod n

A friend recently asked me if I could solve these three problems: (a) Prove that the sequence $ 1^1, 2^2, 3^3, \dots \pmod{3}$ in other words $\{n^n \pmod{3} \}$ is periodic, and find the length of ...
13
votes
1answer
623 views

Find the positive integer solutions of $m!=n(n+1)$

Find the positive integer solutions of $m!=n(n+1)$ I basically have $(m,n)=(2,1)$ or $(3,2)$ and I think these are the only solutions. I don't have a complete proof but here's what I know so far. By ...
13
votes
2answers
260 views

How did Letac solve $x_1^k + x_2^k + \dots +x_9^k = 0$ for $k = 1, 3, 5, 7$ in 1942?

It's quite easy to find integer solutions to, $$x_0^k + x_1^k + \dots +x_9^k = 0$$ for $k = 1, 3, 5, 7$. One I found is, if $x^2-10y^2 = 9$, then, $$1 + 5^k + (3+2y)^k + (3-2y)^k + (-3+3y)^k + ...
13
votes
1answer
206 views

Integer Sequence “sums of digits of squares”.

For all $n \in \mathbb{N}$ we define the function $\delta(n)=p$, where $p$ is sums of digits of $n^2$. For example if $n=17, \ n^2=289$, then $\delta(17)=2+8+9=19$. Let $a_k$ is a monotonically ...
13
votes
1answer
366 views

Roots with equal fractional parts

Question. ¿Does there exist an integer $n>1$ such that there exist positive integers $a,b$ such that $\{\sqrt[n]{a}\}=\{\sqrt[n]{b}\},a\neq b$ and $a$ and $b$ aren't perfect n-th powers? ( $\{x\}$ ...
13
votes
1answer
545 views

My attempt to prove GCD exists

Please review my attempt to prove a theorem. Any mistakes you point would be highly appreciated by me. To prove the theorem, I'll be using the following properties which I'm assuming have already ...
13
votes
2answers
370 views

Prove that: $x_1\cdot x_2\cdots x_n>y_1\cdot y_2\cdots y_m$.

For two positive integer sequences $x_1,x_2,\ldots,x_n$ and $y_1,y_2,\ldots,y_m$ satisfying $x_i\neq x_j\quad \text{and}\quad y_i\neq y_j\quad \forall i,j, i \ne j$ ...
13
votes
1answer
377 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 ...
13
votes
0answers
202 views

How to find all functions $f$ such that $f(a)+f(b)$ is square number, if $a+b$ is square number.

Question: For any $a,b\in N^{+}$, if $a+b$ is square number, then $f(a)+f(b)$ is also a square number. Find all such functions. My try: It is clear that the function $$f(x)=x$$ satisfies the ...
12
votes
6answers
3k views

Prime factorization of 1

Fundamental Theorem of Arithmetic says every positive number has a unique prime factorisation. Question: If 1 is neither prime nor composite, then how does it fit into this theorem?
12
votes
2answers
810 views

Is this number rational?

Consider the following number: $x=0.01001000100001...$ (the number of '$0$' between '$1$'s increases linearly) given by the sum $$x=\sum_{i=1}^\infty 10^{-i - i (1 + i)/2}$$ My question is ...
12
votes
4answers
12k 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 ...
12
votes
5answers
2k 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 ...
12
votes
7answers
471 views

How can I find the possible values that $\gcd(a+b,a^2+b^2)$ can take, if $\gcd(a,b)=1$

If $\gcd(a,b)=1$, how can I find the values that $\gcd(a+b,a^2+b^2)$ can possibly take? I can´t find a way to use any of the elemental divisibility and gcd theorems to find them.
12
votes
6answers
1k views

Does the formula $\sqrt{ 1 + 24n }$ always yield prime?

I did some experiments, using C++, investigating the values of $\sqrt{1+24n}$. ...
12
votes
2answers
814 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!\,\,?$
12
votes
4answers
226 views

What is the largest integer with only one representation as a sum of five nonzero squares?

It seems to be very well known that $33$ is the largest integer with zero representations as a sum of five nonzero squares. So it seems reasonable to me that as we go higher and higher, numbers have ...
12
votes
11answers
12k views

Proof that $n^3+2n$ is divisible by 3

I'm trying to freshen up for school in another month, and I'm struggling with the simplest of proofs! Problem: For any natural number n , n3 + 2n is divisible by 3. This makes sense ...
12
votes
4answers
1k views

Proof that $x^2+4xy+y^2=1$ has infinitely many integer solutions

The question would, naturally, be very straight forward if there was a $2xy$ instead of a $4xy$. Then it would simply be a matter of doing: $$ x^2+2xy+y^2=1\\ (x+y)^2=1\\ \sqrt{(x+y)^2}=\sqrt{1}\\ ...
12
votes
2answers
150 views

How can I prove analytically the number $2^{100000}+1$ is not prime??

How can I prove analytically the number $$(2^{100000}+1)$$ is not prime??
12
votes
2answers
535 views

If 1 boy knows r girls and 1 girl knows r boys ,then number of boys=girls

Yet another question from BdMO 2013 Nationals: In a class,every boy knows $r$ number of girls and every girl knows $r$ number of boys.Show that there are equal number of boys and girls[Assume that ...
12
votes
5answers
528 views

Prove that there are infinitely many natural numbers $n$, such that $n(n+1)$ can be expressed as sum of two positive squares in two distinct ways.

Prove that there are infinitely many natural numbers $n$, such that $n(n+1)$ can be expressed as sum of two positive squares in two distinct ways.($a^2+b^2$, is same $b^2+a^2$), $n \in \mathbb{N}.$ ...
12
votes
2answers
255 views

Diophantine equation: $x^2+y^2+z^2=n(xy+yz+zx)$

Let $x,y,z\in \mathbb{Z}$. Find all naturals $n$ such that the equation $x^2+y^2+z^2=n(xy+yz+zx)$ has nontrivial solution(s) (i.e. other than $(0,0,0)$), or prove there exist none. Note: I have ...
12
votes
4answers
605 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 ...
12
votes
2answers
413 views

For $n \geq 2$, show that $n \nmid 2^{n}-1$

Here is a problem which i have not been able to do for quite sometime. For $n \geq 2$, show that $n \nmid 2^{n}-1$. I have thought of proving this in two ways: One by using induction which didn't ...
12
votes
5answers
390 views

How many prime numbers are there in between $1000!+1$ and $1000!+1000$, inclusive?

I know $1000!$ is not a prime number as any number $1000$ or less is a divisor, but how would I know if $1000!+1$ is prime? Any hints? Also, use the above question to prove that you can find $n$ ...
12
votes
3answers
321 views

$x^2+xy+y^2$ and $x^2-xy+y^2$ are not both perfect squares

Prove that $x^2+xy+y^2$ and $x^2-xy+y^2$ cannot be both perfect squares. Surely $x$ and $y$ are natural numbers. If $x^2+xy+y^2 =a^2$ and $x^2-xy+y^2=b^2$ simultaneously then we have to show that ...