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

learn more… | top users | synonyms

12
votes
2answers
789 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
5answers
1k 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
5answers
29k views

How to find the inverse modulo m?

For example: $$7x \equiv 1 \pmod{31} $$ In this example, the inverse of $7$ is $9$. How can we find out that $9$? What are the steps that I need to do? Update If I have a general modulo equation: ...
12
votes
7answers
448 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
4answers
198 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
4answers
866 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
6answers
413 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 ...
12
votes
4answers
5k views

How to use the Extended Euclidean Algorithm manually?

I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
12
votes
2answers
485 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
2answers
251 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 ...
12
votes
2answers
407 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
3answers
311 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 ...
12
votes
4answers
398 views

How many powers of 2 are easy to double? [duplicate]

Possible Duplicate: Is 2048 the highest power of 2 with all even digits (base ten)? Numbers written in base $10$ are easiest to double when their digits lie in the range $0, \ldots, 4$, so ...
12
votes
3answers
567 views

Prove that if $p$ is an odd prime that divides a number of the form $n^4 + 1$ then $p \equiv 1 \pmod{8}$

Problem Prove that if $p$ is an odd prime that divides a number of the form $n^4 + 1$ then $p \equiv 1 \pmod{8}$ My attempt was, Since $p$ divides $n^4 + 1 \implies n^4 + 1 \equiv 0 \pmod{p} ...
12
votes
4answers
189 views

how to solve $1!+2!+3!+…+x!=y^{z+1}$where $x,y,z\in \mathbb N$?

how to solve the following equation where $x,y,z\in \mathbb N$ $$1!+2!+3!+...+x!=y^{z+1}$$ Thanks in advance
12
votes
5answers
307 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
1answer
1k 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 ...
12
votes
3answers
182 views

What is the order of $2$ in $(\mathbb{Z}/n\mathbb{Z})^\times$?

Is it there some theorem that makes a statement about the order of $2$ in the multiplicative group of integers modulo $n$ for general $n>2$?
12
votes
3answers
409 views

Number Theory or Algebra?

Prove that if $4^m-2^m+1$ is a prime number, then all the prime divisors of $m$ are smaller than $5$ I initially thought about putting $4^m-2^m+1=p$ where $p$ is some prime and after eliminating ...
12
votes
2answers
278 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 ...
12
votes
1answer
2k views

Proof of Euler's Theorem without abstract algebra?

Every proof I've seen of Euler's Theorem (that $\gcd(a,m) = 1 \implies a^{\phi(m)} \equiv 1 \pmod m$) involves the fact that the units of $\mathbb{Z}/m\mathbb{Z}$ form a group of order $\phi(m)$. ...
12
votes
3answers
209 views

A conjecture: for all $n\in\mathbb{N}$, the least $k>1$ such that $\phi(k)\geqslant n$ is a prime

I came across a problem in book that asked us to find the first number $n$ such that $\phi(n)\geqslant 1,000$ it turns out that the answer is 1009, which is a prime number. There were several ...
12
votes
1answer
139 views

Solving $n!+m!+k^2=n!m!$ for positive integers $n,m,k$

I have been running in circles with this for a while now. It seems that the only solution is $(n,m,k)=(2,3,2)$ but I don't know how to prove it. Things I have noticed: WLOG $n\geq m$ we see that ...
12
votes
2answers
162 views

A problem in fractions from a very old arithmetic textbook

Similar in vein to a problem I posted before here, I would be interested if anyone can give me any pointers as to how one might solve this question from the same arithmetic textbook: "Simplify ...
12
votes
1answer
650 views

Sum of powers and prime numbers

I'm not able to find solutions of the following equation: $$2^k+3^k=p$$ where $p$ is a prime number and $k \in N$. It's easy to show that we have a solution when $k=1,2,4$. Is it possible to find any ...
12
votes
1answer
130 views

Twelve Distinct Positive Integers

Let S be a set of twelve distinct positive integers such that for distinct a, b, c, and d in S, a + b ≠ c + d. Show that the largest element in S is greater than 56. I found some math competition ...
12
votes
1answer
367 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 ...
12
votes
3answers
498 views

$(2^m -1)(2^n-1)$ divides $(2^{mn} -1)$ if and only if $\gcd(m,n) = 1$.

If $\gcd(m,n) = 1$ then $(2^m-1)(2^n-1)$ divides $2^{mn} - 1$ because each of $2^m-1$, $2^n-1$ divide $2^{mn}-1$ and $\gcd(2^m-1, 2^n-1) = 2^{\gcd(m,n)}-1 = 1$. How about the converse? If $\gcd(m,n) ...
12
votes
1answer
298 views

$a^m+k=b^n$ Finite or infinite solutions?

Given positive integers k,a,b, is there a finite or infinite number of solutions in positive integers $m,n>1$, to $a^m+k=b^n$? Pillai's conjecture states that each positive integer occurs only ...
12
votes
1answer
263 views

If the product of $x$ positive integers is $n!$ What is the smallest possible value their sum can have?

If the product of $x$ positive integers is $n!$ What is the smallest possible value their sum can have? I was wondering what could be the most efficient strategy to solve this problem for ...
12
votes
0answers
499 views

A very nice divisibility problem

A very hard problem, here it is: Prove that, if $2^{2^j} a + 1$ divides $c^{2^j}+1$ for fixed integers $a,c$ and all nonnegative integers $j$, then $a=1$ and $c=2^l$ for some odd positive integer ...
11
votes
7answers
748 views

Prove: $\frac{n^5}5 + \frac{n^4}2 + \frac{n^3}3 - \frac n {30}$ is an integer for $n \ge 0$

I am attempting to prove the following problem: Prove that $\frac{n^5}5 + \frac{n^4}2 + \frac{n^3}3 - \frac n {30}$ is an integer for all integers $n = 0,1,2,...$ I attempted to solve it by ...
11
votes
6answers
2k views

If an inequality is true for all natural numbers, is it necessarily true for all real numbers inbetween?

A lot of the time in lectures, my professors prove (by induction) an inequality (e.g. $(1+x)^n \geq 1+nx$) in the natural numbers (or any subsets thereof), and I've noticed (not rigourously; only by ...
11
votes
6answers
2k 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?
11
votes
4answers
10k 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 ...
11
votes
5answers
2k views

Prove a number is composite

How can I prove that $$n^4 + 4$$ is composite for all $n > 5$? This problem looked very simple, but I took 6 hours and ended up with nothing :(. I broke it into cases base on quotient remainder ...
11
votes
4answers
440 views

Partitioning the naturals into an infinite number of large sets

Is it possible to partition the positive integers into an infinite number of disjoint large sets ?
11
votes
2answers
742 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!\,\,?$
11
votes
3answers
478 views

Fermat's last theorem — Google and PCMag.com

In recognition of Fermat's 410th birthday, Google ha(s/d) a special google-doodle with Fermat's last theorem. The first link point(s/ed) to an article on PCMag.com which states: In time, Fermat ...
11
votes
3answers
10k views

How to find solutions of linear Diophantine ax + by = c?

I want to find a set of integer solutions of Diophantine equation: $ax + by = c$, and apparently $gcd(a,b)|c$. Then by what formula can I use to find $x$ and $y$ ? I tried to play around with it: $x ...
11
votes
3answers
339 views

Is there a direct, elementary proof of $n = \sum_{k|n} \phi(k)$?

If $k$ is a positive natural number then $\phi(k)$ denotes the number of natural numbers less than $k$ which are prime to $k$. I have seen proofs that $n = \sum_{k|n} \phi(k)$ which basically ...
11
votes
11answers
9k 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 ...
11
votes
2answers
286 views

Prove that $n^{2003}+n+1$ is composite for every $n\in \mathbb{N} \backslash\{1\}$

Prove that $n^{2003}+n+1$ is composite for every $n\in \mathbb{N} \backslash\{1\}$. I tried with expanding $n^{2003}+1$, but I got nothing pretty not useful. I also couldn't get any improvement, let ...
11
votes
1answer
182 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 ...
11
votes
3answers
322 views

Irrationality of $\sqrt 2$ using induction

I came upon this exercise in a textbook. I know that $\frac{n}{b} \ne \sqrt{2} $ for all $b \gt 0$ and $n \le N_0$. How can I then show that $\frac{N_0 + 1}{b} \ne \sqrt{2}$ for all $b \gt 0$?
11
votes
6answers
649 views

Divisibility of large number

This was a question asked in a competitive exam: $(300^{3000} -1 )$ is divisible by a) $401$ b) $501$ c) $301$ d) $901$ The answer is $301$. Not sure how they arrived at the answer. Can ...
11
votes
2answers
237 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 ...
11
votes
4answers
1k views

Showing $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$

Given that n is a positive integer show that $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, or $9$. I'm thinking that I should be using the property of gcd that says if a and b are integers then gcd(a,b) = ...
11
votes
5answers
949 views

If $(a^{n}+n ) \mid (b^{n}+n)$ for all $n$, then $ a=b$

I happened to receive this from my friend. Let $a,b \in \mathbb{N}$, such that $a^{n}+n \: \bigl|\: b^{n}+n$ for all $n \in \mathbb{N}$. Prove that $a=b$. How do we proceed?