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

learn more… | top users | synonyms

10
votes
2answers
185 views

If $n\in\mathbb N$ and $4^n+2^n+1$ is prime, prove that there exists an $m\in\mathbb N\cup\{0\}$ such that $n=3^m$.

If $n\in\mathbb N$ and $4^n+2^n+1$ is prime, prove that there exists an $m\in\mathbb N\cup\{0\}$ such that $n=3^m$. I.e. if $4^n+2^n+1$ is prime, prove that $n=3^m$, where $m\in\mathbb N\cup\{0\}$. ...
2
votes
1answer
75 views

If $p$ is prime and $p>3$ and $k,l,m,n,p\in\mathbb N$ and $p^k+p^l+p^m=n^2$, prove that $8\mid p+1$.

If $k,l,m,n,p\in\mathbb N$ and a prime number $p>3$ that satisfies $$p^k+p^l+p^m=n^2$$ is chosen, prove that $8\mid p+1$. $n^2$, when divided by $8$, gives a remainder $1$ (it can't give the ...
4
votes
1answer
172 views

Diophantine Equation in $\mathbb{Z}$

I would like to know how to solve $2x^2 - y^{14} = 1$ in integers. I've transformed it into $(y^7 - 1)^2 + (y^7 + 1)^2 = (2x)^2$ and I have stopped here.
0
votes
3answers
90 views

How do I calculate the remainder of $13^{13^{13}} \mod 22$

I have been looking into number theory, but I cannot get the hang of calculating remainders of numbers with multiple exponents such as $$ 13^{13^{13}} \mod 22 $$ So far I have calculated that $13 ...
0
votes
2answers
87 views

Sum and difference equal to squares

Can anyone help me to find the integer solutions of these equations? \begin{align} (w^2-r^2)+(s^2-k^2)&=t_1^2\\ (w^2-r^2)-(s^2-k^2)&=t_2^2 \end{align} It can be written as \begin{align} ...
5
votes
3answers
222 views

What is the smallest natural number n?

What is the smallest natural number n for which there is a natural k, such that, the lasts 2012 digit in the representation decimal of $n^k$ are equal to 1? I don't even know how to start with it ... ...
0
votes
1answer
65 views

Congruence not a square

How to show that $5i+3\mod 12i+7$ is not an integer square, for any integer $i\in\mathbb{Z}$ ? I do not see where to start. Thanks in advance. @ Ragnar Thanks. I would like to show that $M\neq ...
3
votes
0answers
98 views

Any new axioms for the natural numbers since Peano?

Have any axioms in addition to usual 2nd-order Peano axioms been found to significantly extend the class of derivable propositions about natural numbers?
0
votes
1answer
80 views

Diophantine equation has at least $k$ positive integer solutions

$k$ is a positive integer. Could we find all the pairs of positive integers $(a,b)$ such that the Diophantine equation $$x(x+a)=y(y+b)$$ has at least $k$ positive integer solutions $(x,y)$, that is ...
6
votes
2answers
473 views

What is the remainder when $1! + 2! + 3! +\cdots+ 1000!$ is divided by $12$?

What is the remainder when $$1! + 2! + 3! +\cdots+ 1000!$$ is divided by $12$. I tried to do it using binomial theorem but that doesn't help. How will we do this? Please help.
3
votes
1answer
68 views

Elementary number theory problem

Let $X = \{n \in \mathbb{N}: 6 \times n\,\, \text{does not consist of} \ 0,1,2,3 \, \text{or} \ 4\}.$ For eg, $93 \in X$ because $6 \times 93=558.$ Could anyone advise me how to prove there ...
1
vote
5answers
379 views

Direct proof: $\sqrt{13}$ is irrational

Show that $\sqrt{13}$ is an irrational number. How to direct proof that number is irrational number. So what is the first step.....
11
votes
2answers
239 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 ...
0
votes
1answer
83 views

Proof that the euler totient function is multiplicative, correctness?

I've tried proving that $\varphi(mn) = \varphi(m)\varphi(n)$ (if $gcd(mn)=1$). The proof I try to setup doesn't look like the proof I find in textbooks, where am I going wrong? Proof: We try to ...
3
votes
0answers
154 views

How many times is the digit $3$ repeated in $9^{666}$? [closed]

How many times is the digit $3$ repeated in the number $9^{666}$ ? Thanks.
5
votes
2answers
154 views

The last three digits of $3\times7\times11\times15\times \cdots \times 2003$ [closed]

How I can find the last three digits of $n$ $$n=3\times7\times11\times15\times \cdots \times 2003?$$
0
votes
1answer
53 views

Generating of primes in base-3 edited

How to prove the following statement! for example primes $p_1$ = $7$ = $n$ and $p_2$ = $13$ = $2n-1$(each prime is $> 3$), then $m = p_1 p_2$ is a Fermat-pseudo prime in base-3. Can we prove ...
3
votes
2answers
82 views

does $a^2-51b^2=\mp 6$ have a solution for integers?

does $a^2-51b^2=\mp 6$ have a solution for integers? I have tried for many modulos, but could not get much out of them.
10
votes
2answers
158 views

Prove $1^{2007}+2^{2007}+\cdots+n^{2007}$ is not divisible by $n+2$

Prove that for any odd natural number $n$, the number $1^{2007}+2^{2007}+\cdots+n^{2007}$ is not divisible by $n+2$.
3
votes
1answer
88 views

Show that $p$ is prime if the following limit property holds

Let $n$ be a positive integer. Show that $n$ is prime if and only if $$\lim_{r\to \infty}\lim_{s\to\infty} \lim_{t\to\infty} ...
0
votes
2answers
63 views

Need help with this homework question. [closed]

There are $4$ stones weighing a total of $40$ kg. what should be the weights of all stones such that they can measure a weight of $1-40$ kg on a balance weighing machine.
2
votes
1answer
69 views

Number of remainders after dividing $x$

Given a positive integer $x$,how many possible remainders can you get after dividing $x$ by positive integers smaller than it? I have been thinking about this question for some time.Here is an ...
2
votes
1answer
72 views

Modular Arithmetic [Confusion]

"Nathan claims that if you pick a two-digit number whose units digit is odd, but not 5, such as 37, and multiply it by some positive integer n and tell him the last two digits of your result that he ...
1
vote
3answers
505 views

Find all solutions of $1/x+1/y+1/z=1$, where $x$, $y$ and $z$ are positive integers

Find all solutions of $1/x+1/y+1/z=1$ , where $x,y,z$ are positive integers. Found ten solutions $(x,y,z)$ as ${(3,3,3),(2,4,4),(4,2,4),(4,4,2),(2,3,6),(2,6,3),(3,6,2),(3,2,6),(6,2,3),(6,3,2)}$. ...
0
votes
1answer
27 views

Strict order of points within a tolerance on a 2d plane

I have a situation that I want to define a strict order of the points on a 2d plane, such that point1 < point2, which point is represented by (x, y) in real number. I also want that two points are ...
3
votes
3answers
121 views

What is 1's digit of $((183)!+3^{183})$

What is 1's digit of $((183)!+3^{183})$ Can this be said without using a calculator
1
vote
2answers
41 views

Probability problem and number theory

A standard fair 6-sided dice is rolled $n$ times. Let $X_k$ be the spot which faced up inthe k-th round. What is the probability that $X_1+X_2+...+X_n$ is divisible by 7? I tried to solve it by ...
1
vote
0answers
46 views

Fermat Primes re edited [duplicate]

First of all sorry for sending the same question. Is my cited below observations are true? If yes, how to prove? 1) Many of $poulet$ numbers are in the form of $(4^x -1)$/$3$, where $x$ is some ...
3
votes
7answers
357 views

Prove that $n(n^2 - 1)(n + 2)$ is divisible by $4$ for any integer $n$

Prove that $n(n^2 - 1)(n + 2)$ is divisible by $4$ for any integer $n$ I can not understand how to prove it. Please help me.
2
votes
1answer
83 views

Find all the prime numbers $p,q$ that satisfy both $ p\mid q+6$ and $q\mid p+7$.

Some observations: $$\begin{cases}\begin{cases}q+6=pk\Rightarrow q=pk-6\\ p+7=ql\Rightarrow p+7=(pk-6)l\Rightarrow p-pkl=-6l-7\Rightarrow p(kl-1)=6l+7\end{cases} \begin{cases}p+7=ql\Rightarrow ...
11
votes
3answers
320 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, ...
1
vote
1answer
85 views

If $m,n\in \mathbb N$ and $n>m$, prove that $lcm(m,n)+lcm(m+1,n+1)>\frac{2mn}{\sqrt{n-m}}$.

Where $lcm$ is the least common multiple. I've changed it to: $$\frac{mn}{\gcd(m,n)}+\frac{(m+1)(n+1)}{\gcd(m+1,n+1)}>\frac{2mn}{\sqrt{n-m}}$$ Can't see how to continue. Is there a way to ...
7
votes
2answers
124 views

$a,b,n,d\in \mathbb N$. $a,b,d$ are different numbers from the interval $(n^2;n^2+n)$. Prove that it can't be true that $d|ab$.

$a,b,n,d\in \mathbb N$. $a,b,d$ are different numbers from the interval $(n^2;n^2+n)$. Prove that it can't be true that $d\mid ab$. This is an interesting problem and I don't know how to start, so ...
2
votes
1answer
52 views

An Euler problem: How many of these numbers are of the form $a^b$?

How much numbers can be written in the form $a^b$, where $a$ and $b$ are integers that are between $2$ and $100$? How can I start this problem? Any hints please? Thanks!
1
vote
5answers
66 views

LCM of a range of numbers

How would one solve this without a brute force method. Let $1\le n\le 10^{12}$ and $\text{lcm}(16,n)=16n$, find the number of unique $n$.
0
votes
1answer
57 views

Show that $m^4+4n^4$ can be expressed as the sum of four squares of natural numbers

Let $m,n$ be natural numbers and $m\not=n$. Show that $m^4+4n^4$ can be expressed as the sum of four squares of natural numbers. That is, express $m^4+4n^4$ as $A^2+B^2+C^2+D^2$ where $A,B,C,D$ ...
1
vote
1answer
63 views

remainder of the division $2^{1990}/1990$ [duplicate]

How do we find the remainder of the division $2^{1990}/1990$? I actually tried it through Fermat's theorem but couldn't arrive at the answer directly.
2
votes
2answers
56 views

if $a^3 + 2b^3\equiv 0 \pmod {27} $, then $a\equiv b \equiv 0 \pmod 3$

if $a^3 + 2b^3\equiv 0 \pmod {27}$, then $a\equiv b \equiv 0 \pmod 3$ could you please show this. I am just able show $a\equiv b \pmod 3$
1
vote
2answers
151 views

Inverse modulo question?

I know that when gcd(a,b) = 1, a and b are relatively prime. This allows you to write the linear combination aS + bT = 1, where S and T are Bezouts's coefficients. As I understand, one of these ...
1
vote
2answers
32 views

if $3^3 2^2 \ | a^2$ then $3^2 2 \ | a $ where a is integer

if $3^3 2^2 \ | a^2$ then $3^2 2 \ |a $ where a is integer. I just cannot see it. please explain this trivial remark.
6
votes
3answers
76 views

Let $R = \mathbb Z[i]$. Show $I \cap \mathbb Z$ is an ideal in $\mathbb Z$, for all $a \in I \cap \mathbb Z$, $10 \mid a^2 = N(a)$.

Let $R = \mathbb Z[i]$, $z = 3+i$ and $I = \langle z \rangle$. I need to show $I \cap \mathbb Z$ is an ideal in $\mathbb Z$, for all $a \in I \cap \mathbb Z$, $10 \mid a^2 = N(a)$ and $10 \mid a$, ...
3
votes
3answers
83 views

Dirichlet series for inverse of Eta function

We know that $$ \frac{1}{\zeta (s)} = \sum_{n=1}^{\infty} \frac{\mu(n)}{n^{s}} $$ but what happens with $$ \frac{1}{\eta (s)} = \sum_{n=1}^{\infty} \frac{b(n)}{n^{s}} $$ with $ \eta (s) = ...
0
votes
5answers
168 views

Questions about Divisibility of $2^n$ by $3$

Why is it that $\forall n \in N$, $2^n$ is not divisible by $3$? I can prove it easily by induction, but I don't understand the intuition of why this is true. Could anyone please supply the ...
5
votes
2answers
90 views

squares which are not the sum of a square and twice a triangular number

I'm trying to determine conditions on integer squares which cannot be written as a square and twice a triangular [all numbers positive], i.e. integers $n \ge 1$ where there are no integers $a,b \ge 1$ ...
2
votes
3answers
139 views

Can equality be defined within a tolerance?

Can equality of two real number be defined within a tolerance? Say, 0 = 0.000009 given the tolerance to be 0.00001. I also assume that equality should be transitive, e.g. a = b, b = c, then a = c. ...
3
votes
4answers
88 views

Let $x,y,z$ be integers and $11$ divides $7x+2y-5z$. Show that $11$ divides $3x-7y+12z$.

Let $x,y,z$ be integers and $11$ divides $7x+2y-5z$. Show that $11$ divides $3x-7y+12z$. I know a method to solve this problem which is to write into $A(7x+2y-5z)+11(B)=C(3x-7y+12z)$, where A ...
5
votes
6answers
334 views

What is the point of quadratic residues?

What is the most motivating way to introduce quadratic residues? Are there any real life examples of quadratic residues? Why is the Law of Quadratic Reciprocity considered as one of the most ...
4
votes
1answer
84 views

Simple method for $\frac{(2n+1)!}{(n!)^{2}}$ divide $lcm(1,2,\ldots,2n+1)$

The question is to prove that $\frac{(2n+1)!}{(n!)^{2}}$ divides $lcm(1,2,\ldots,2n+1)$. This seems like it should be a simple question, but try as I might, I can't seems to find any way that does ...
-4
votes
2answers
50 views

number of common multiples of 12 & 14 [closed]

How can I solve this problem: how many common multiples of $12$ & $14$ are there less than $288$?
0
votes
1answer
57 views

Remainder Theorem application

The remainder theorem of elementary algebra states that if $P(x)$ is a polynomial in $x$ and $r$ is all real, then there exists a polynomial $Q(x)$ $$P(x)=Q(x)(x-r)+P(r)$$ a. Show that $$\lim_{x\to ...