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

learn more… | top users | synonyms (1)

19
votes
4answers
2k views

Is the number $333{,}333{,}333{,}333{,}333{,}333{,}333{,}333{,}334$ a perfect square?

I know that if the number is a perfect square then it will be congruent to $0$ or $1$ (mod $4$). Now since the number is even, I know that it is either $0$ or $2$ (mod $4$). How would I go about ...
19
votes
2answers
546 views

not both $2^n-1,2^n+1$ can be prime.

I am trying to prove that not both integers $2^n-1,2^n+1$ can be prime for $n \not=2$. But I am not sure if my proof is correct or not: Suppose both $2^n-1,2^n+1$ are prime, then $(2^n-1)(2^n+1)=4^n-...
19
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 ...
19
votes
3answers
4k views

Why does (1/3) mod 3016 = 2011?

So I am taking a class where we are working on a cryptography section. Basically, the course says that: $$\frac 1 3 \mod(3016) = 2011$$ or when run through Python - modified with SciPi: $$\frac 1 3 \,...
19
votes
5answers
4k views

Proving that all integers are even or odd [duplicate]

I know that $\mathbb{Z}$ is a group under addition with a multiplication defined. I have just the definition of even and odd integers: $n$ is even if $n = 2k$ for some integer $k$ and $n$ is odd if $n ...
19
votes
6answers
5k 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 ...
19
votes
5answers
1k views

How does one show that two general numbers $n! + 1$ and $(n+1)! + 1$ are relatively prime?

How does one show that two general numbers $n! + 1$ and $(n+1)! + 1$ are relatively prime? I don't mind if someone uses a different example, I want to learn how to prove this class of problems. My ...
19
votes
3answers
4k views

Is there an elementary proof for Fermat's last theorem?

I wonder is there an elementary proof for Fermat's last theorem. Why it's so difficult to prove this theorem by elementary method? Thanks,
19
votes
3answers
2k views

Prove that there exists a number divisible by 1999 with digit sum 1999

My nephew in the secondary school asked me how to solve the problem as stated in the title. Honestly, I do not have any idea how to do it: Prove that there exists a positive integer number such ...
19
votes
4answers
4k views

How can I prove that $\gcd(a,b)=1\implies \gcd(a^2,b^2)=1$ without using prime decomposition?

How can I prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$, without using prime decomposition? I should only use definition of gcd, division algorithm, Euclidean algorithm and corollaries to those. ...
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
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 $[0,1]...
19
votes
2answers
556 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?
19
votes
2answers
510 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 ...
19
votes
2answers
588 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 ...
19
votes
2answers
201 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
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 ...
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, \ldots\}...
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
26k 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
11k 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
626 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
961 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) = a^4+4a^3+6a^2+...
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
6answers
657 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 ...
18
votes
5answers
1k 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 x$...
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
504 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 $pq|2^{p-1}...
18
votes
2answers
386 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. But I ...
18
votes
3answers
1k 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 $P$...
18
votes
1answer
329 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}$$ $$\sin\frac{2\pi}{11}-\sin\frac{4\pi}{11}+\sin\frac{6\pi}{11}+\sin\frac{8\pi}{11}+\sin\...
18
votes
3answers
172 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
675 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 $y^2+nx^2$...
18
votes
1answer
689 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
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 ...
18
votes
2answers
515 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
251 views

Finding primes so that $x^p+y^p=z^p$ is unsolvable in the p-adic units

On my number theory exam yesterday, we had the following interesting problem related to Fermat's last theorem: Suppose $p>2$ is a prime. Show that $x^p+y^p=z^p$ has a solution in $\mathbb{Z}_p^{\...
18
votes
0answers
760 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
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
4answers
2k views

Have I found all the numbers less than 50,000 with exactly 11 divisors?

The math problem I am trying to solve is to find all positive integers that meet these two conditions: have exactly 11 divisors are less than 50,000 My starting point is a number with exactly 11 ...
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
2answers
803 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
2answers
964 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
1answer
419 views

All elements in $\mathbb{Z}/n\mathbb{Z}$ are representable as sum of a square and a cube?

Is it true that all elements in $\mathbb{Z}/n\mathbb{Z}$ are representable as the sum of a square and a cube? Example: ($n=7$) $0 \equiv 0^2+0^3 \left( \text{mod } 7 \right)$ $1 \equiv 1^2+0^3 \...
17
votes
4answers
472 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: ...