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

learn more… | top users | synonyms

12
votes
2answers
248 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
404 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
303 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
393 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
565 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
188 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
295 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
181 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
2answers
273 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
394 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
3answers
208 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
138 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
381 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 ...
12
votes
1answer
183 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 ...
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
365 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
490 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
609 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
297 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
260 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
466 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
743 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

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
439 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
726 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
5answers
28k 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: ...
11
votes
3answers
475 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
9k 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
329 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
2answers
285 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
6answers
637 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
230 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
947 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?
11
votes
2answers
218 views

Prove that $2xy\mid x^2+y^2-x$ implies $x$ is a perfect square.

Prove that $2xy\mid x^2+y^2-x$ implies $x$ is a perfect square. My work: $2xy\mid x^2+y^2-x \implies x^2+y^2-x=2xy\cdot k$ So,$x^2+y^2+2xy-x=(x+y)^2-x=2xy \cdot (k+1)$ And,$x^2+y^2-2xy-x=(x-y)^2-x=2xy ...
11
votes
5answers
426 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}.$ ...
11
votes
7answers
1k views

Proof that the sum of the cubes of any three consecutive positive integers is divisible by three.

So this question has less to do about the proof itself and more to do about whether my chosen method of proof is evidence enough. It can actually be shown by the Principle of Mathematical Induction ...
11
votes
3answers
344 views

Fermat: Last two digits of $7^{355}$

I am doing this problem mentioned above and I know the answer because I know Euler's Theorem that $$a^{\varphi{(m)}}\equiv{1}\pmod{m}.$$ I used 100 as my modulus and got that the last two digits of ...
11
votes
2answers
324 views

product is twice a square

For every positive integer $n$, there exists a set $S\subset \{n^2+1,n^2+2,\dotsc,(n+1)^2-1\}$, such that $$\prod_{k\in S}k=2m^2$$ for some positive integer $m$ I have no clue about it. Could ...
11
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 ...
11
votes
2answers
114 views

Find the minimum of $q$.

Given $\displaystyle p,q\in\mathbb N, \frac p q=0.123456789...$(i.e. the first 9 digits after decimal point are $123456789$). Find the minimum of $q$. I guessed the answer to be $111111111$ as ...
11
votes
4answers
643 views

Proof that $n^3 + 3n^2 + 2n$ is a multiple of $3$.

I'm struggling with this problem: For any natural number $n$, prove that $n^3 + 3n^2 + 2n$ is a multiple of $3$. That $n^3 + 3n^2 + 2n$ is a multiple of $3$ means that: $n^3 + 3n^2 + 2n = 3 ...
11
votes
2answers
345 views

Showing $x < \frac{\Phi(n+2)}{\Phi(n)} < y$ for $x,y \in \mathbb{R}$

Happened to get this from a friend. How does one show that for all pairs of real numbers $x$ and $y$, there is $n \in \mathbb{N}$ such that $$ x < \frac{\Phi(n+2)}{\Phi(n)} < y$$ where $\Phi$ ...
11
votes
3answers
298 views

Why are conjectures about the primes so hard to prove?

I recently started learning number theory, and I've noticed there are many conjectures about the prime numbers that are unproven. Some examples would be whether there are infinite Mersenne, ...
11
votes
5answers
240 views

Prove $2^b-1$ does not divide $2^a + 1$ for $a,b>2$

I'm trying to prove $2^b-1$ does not divide $2^a + 1$ for $a,b>2$. Can someone give a hint in the right direction for this?
11
votes
2answers
159 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 ...
11
votes
2answers
609 views

How would proving or disproving the Twin Prime Conjecture affect proving or disproving the Riemann Hypothesis if at all?

How would proving or disproving the Twin Prime Conjecture affect proving or disproving the Riemann Hypothesis? What are the connections between both conjectures if any?