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

learn more… | top users | synonyms

14
votes
3answers
392 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
318 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$?
14
votes
1answer
141 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$ ...
13
votes
4answers
688 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
8answers
861 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
934 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
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 ...
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
532 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
8answers
1k views

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

I did some experiments, using C++, investigating the values of $\sqrt{1+24n}$. ...
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
1answer
215 views

Is the equation $\phi(\pi(\phi^\pi)) = 1$ true? And if so, how?

$\phi(\pi(\phi^\pi)) = 1$ I saw it on an expired flier for a lecture at the university. I don't know what $\phi$ is, so I tried asking Wolfram Alpha to solve $x \pi x^\pi = 1$ and it gave me a bunch ...
13
votes
3answers
611 views

Can Number Theory be visualized?

So I was thinking about a hard euclidean geometry problem, when it hit me just how much more difficult it would become without the aid of a diagram. This got me thinking: Wouldn't it be great if we ...
13
votes
3answers
2k 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
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
689 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
2answers
3k 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
153 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
305 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
485 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
2answers
3k views

What is complete induction, by example? $4(9^n) + 3(2^n)$ is divisible by 7 for all $n>0$

So, I've been revising for an exam and I came up against the question " prove $4(9^n) + 3(2^n)$ is divisible by 7 for all $n>0$. Now, I know how to do this. If I assume $n=k$ divisible by $7$, ...
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
435 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
372 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
473 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
639 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
263 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
212 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
370 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
552 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
375 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
380 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
244 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 + ...
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
816 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
13k 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
7answers
493 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
4answers
236 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
563 views

If each boy knows r girls and each 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
4answers
187 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.....$$
12
votes
5answers
553 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}.$ ...