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

learn more… | top users | synonyms (1)

2
votes
1answer
104 views

Given $(a,4)=2, (b,4)=2$, prove $(a+b,4)=4$

So if $(a,4)=2,$ then $a=4k+2$, for some integer $k$ if $(b,4)=2$, then $b=4m+2$, for some integer $m$ Then $a+b=4(k+m)+4=4(k+m+1)$ So $a+b$ is a multiple of $4$, and thus, $(a+b,4)=4$. Are my ...
2
votes
2answers
419 views

Three primitive Pythagorean triples with the same c

Can someone give me an example of Three primitive Pythagorean triples with the same c?
4
votes
4answers
204 views

Prove that $(4/5)^{\frac{4}{5}}$ is irrational

Prove that $(4/5)^{\frac{4}{5}}$ is irrational. My proof so far: Suppose for contradiction that $(4/5)^{\frac{4}{5}}$ is rational. Then $(4/5)^{\frac{4}{5}}$=$\dfrac{p}{q}$, where $p$,$q$ are ...
5
votes
1answer
43 views

prove $(F_nF_{n+3})^2+(2F_{n+1}F_{n+2})^2=F_{2n+3}^2$

Can anyone give me some hint or start point for proof of this following identity, please? $$(F_nF_{n+3})^2+(2F_{n+1}F_{n+2})^2=F_{2n+3}^2$$ I used a lot of ways and identities and couldn't arrive to ...
3
votes
2answers
105 views

Query about Reductio Ad Absurdum

If we use the method of contradiction(i.e.Reductio Ad Absurdum), and if one of our assumptions is wrong, does that mean that all our assumptions are wrong and is the statement or hypothesis proved?
5
votes
1answer
149 views

Proof $2^{1092}-1$ is divisible by $1093^2$?

I would like a proof that $2^{1092}-1$ is divisible by $1093^2$. I can prove it is divisible by $1093$ by using Fermat ($1093$ is a prime) or Euler. However I'm pretty sure we are going to have to ...
6
votes
3answers
2k views

To prove this sequence does not contain a perfect square [duplicate]

I have to prove that the sequence $\{11,111,1111, \dots \} $ doesn't contain any perfect square numbers. I can realize it but I am unable to prove it. Please help.
2
votes
6answers
282 views

Investigating the linearity between squares and their roots

I recently noticed that $\sqrt{128} = 11.31$ and that $128$ is $\approx 30\%$ between $121 = 11^2$ and $144=12^2$, that is: $$ \frac{128-121}{144-121} = \frac{7}{23} \approx 30\%$$ and $\sqrt{128} = ...
9
votes
4answers
289 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
0answers
516 views

How does a Lehmer Sieve work?

http://en.wikipedia.org/wiki/Lehmer_sieve Apparently a Lehmer Sieve was a mechanical device that used chains and pulleys to factor numbers and solve diophantine equations. It once was able to factor ...
1
vote
0answers
36 views

Is there a Poulet number with this condition?

Is there a Poulet number $n$ with this condition: $◎(n)=\frac{n+1}{2^x}$ or $\ ◎(n)=\frac{n-1}{2^x}, \ x \in \mathbb{N}_{\gt 0}$? (Recall that a Poulet number is a composite $n$ such that $2^n−2$ is ...
6
votes
1answer
83 views

GCD of large numbers of special form

I know that $\gcd(x^n-1,x^m-1) = x^{\gcd(n,m)}-1$. What is the gcd of $x^n+1$ and $x^m+1$? I mean, is there any method to calculate it like the one I have mentioned?
0
votes
2answers
62 views

Prove that $\mathrm{lcm}(n,m)= \mathrm{lcm}(|n|,|m|)$

Prove that $\mathrm{lcm}(m,n)$ exists, that $\mathrm{lcm}(n,m)=\mathrm{lcm}(|n|,|m|)$, and that $|n|*|m|=\gcd(m,n)*\mathrm{lcm}(m,n)$. I have been able to proof the first and third part of the ...
1
vote
2answers
56 views

Let $a$ and $b$ be relatively prime integers. Show that $\gcd(a+b,a^2-3ab+b^2)= 1$ or $5$

Let $a$ and b be relatively prime integers. Show that $\gcd(a+b,a^2-3ab+b^2)=1$ or $5$ Proof: $s\mid (a+b)$ and $s\mid (a^2-3ab+b^2)$ implies $s\mid(a+b)^2=a^2+b^2+2ab$ and $s\mid (a^2-3ab+b^2)$ ...
3
votes
2answers
72 views

Check: For the integers $a,b,c$ show that $\gcd(a,bc)=\gcd(a,\gcd(a,b)\cdot c)$

For the integers $a,b,c$ show that $\gcd(a,bc)=\gcd(a,\gcd(a,b)\cdot c)$ Proof: Let $u$ and $v$ be integers. Then $\gcd(a,b)=au+bv$. Then $c\cdot \gcd(a,b)=c\cdot(au+bv)=acu+bcv$ Let $x$ and $y$ be ...
0
votes
2answers
119 views

CHECK: Let a and b be relatively prime integers. Show that $\gcd(a^2+b^2,a+b)=$1 or 2 [duplicate]

Let a and b be relatively prime integers. Show that $\gcd(a^2+b^2,a+b)=$1 or 2 Proof: $s|a^2+b^2$ and $s|a+b$ implies $s|a^2+b^2$ and $s|(a+b)^2=a^2+b^2+2ab$ implies $s|a^2+b^2-(a+b)^2=2ab$ implies ...
0
votes
1answer
84 views

Unindentified inequality from Hardy-Littlewood-Polya

I found this while trying to understand a theorem. Could anyone tell me which famous inequality is being mentioned here, and where I can find a proof/ statement of that inequality? The article refers ...
1
vote
2answers
41 views

Proving that $p^{\alpha + \beta + 1} \mid {n \choose k} p^{k\alpha}$ when $p^\beta \mid n$.

Let $n,\alpha\in\mathbb{N},\beta\in\mathbb{N}_0$, and let $p$ be odd prime number s.t. $p^\beta|n$. How do we prove that $p^{\alpha+\beta+1}|{n\choose k}p^{k\alpha}$ for every ...
1
vote
1answer
68 views

Does every integer $n > 2$ have an arithmetic expression involving at least two consecutive integers but excluding $n$ itself?

For example: $10 = 1 + 2 + 3 + 4$ $11 = 1 - 2 + 3 \times 4$ $12 = 3 \times 4$ $13 = -(1 - 2) + 3 \times 4$ $14 = 2 + 3 + 4 + 5$ $15 = 1 + 2 + 3 + 4 + 5$ $16 = (2/3)(4/5)(6 + 7 + 8 + 9)$ $17 = ...
1
vote
1answer
94 views

Alternative solution to $\cos\frac{2\pi}{17}$

When I saw Gauss's original solution to $17$ sided gon, his method seemed all clever and tricky. I am wondering if there are some other ways to evaluate $$\cos\frac{2\pi}{17}$$
3
votes
6answers
101 views

Show that $7\mid(3^{2n+1}+2^{n+2})$ for all $n\in\mathbb{N}$

Prove that the following is true for every $n∈ℕ$: $$7\mid(3^{2n+1}+2^{n+2}).$$ I've noticed $$3^{2n+1}+2^{n+2} =3^{2n} \cdot 3+2^{n} \cdot 4.$$ Any suggestions how to continue from there to ...
0
votes
0answers
56 views

For all prime $\ p > \ 2,\ p=2^x \cdot Ord_p(2)+1$?

For all prime $\ p\ > \ 2,\ p=2^x \cdot Ord_p(2)+1?\ $ Where $\ x \in \mathbb{Z}_{\geq 0}.\ $ Such as $\ Ord_3 (2) = 2, \ 3=2^0 \cdot 2 + 1$. Is there some way to prove this?
2
votes
2answers
116 views

Proving a Pellian connection in the divisibility condition $(a^2+b^2+1) \mid 2(2ab+1)$

I'm trying to prove that all integer solutions $a > b \ge 0$ to the divisibility condition in the title, namely $$(a^2+b^2+1) \mid 2(2ab+1),$$ are given by ...
1
vote
2answers
44 views

Proof relating to the order of $a \mod n$?

The proof required is to show that $\operatorname{ord}_n(a^j) \mid\operatorname{ord}_n(a)$, for any positive integer $j$. I have considered using a proof by contradiction, but am having trouble going ...
2
votes
1answer
113 views

Going through all Bit Strings with no 11 in it (no consecutive 1s)

My question is very simple: How can i (efficiently) go through all Bitstrings which don't contain two consecutive 1s? So for instance, all Bitstrings of length 3 with no consecutive 1s are: 000, 001, ...
2
votes
1answer
99 views

Help a Beginner with a Number Theory question?

I just started doing some AMC questions out of a problem-solving book that was lying around my house. I was wondering if you could advise me on how to approach these problems, and give me a hint on ...
2
votes
1answer
102 views

The Elementary number theory problem

I have to prove the following: if $a$, $b$, $n \in \mathbb N$ and $\frac{a^k}{b^{k-1} n^k} \in \mathbb Z$ for every $k \in \mathbb N$ then $\frac {a}{bn} \in \mathbb Z$. I was said that this is an ...
0
votes
1answer
154 views

Adding a natural number to a normalized fraction

I am currently writing yet another rational number class where the fraction should always be normalized. When adding a natural number to a normalized fraction, it possible to get a non-normalized ...
0
votes
1answer
213 views

What is the remainder when $24^{1202}$ is divided by $1446$?

I tried remainder theorem but that does not simplify it. I tried factorizing $1446$ as $2\cdot3\cdot241$ and got remainders when numerator is divided by $2,3$ and $241$ individually but then I did ...
1
vote
0answers
109 views

Zero divided by zero [duplicate]

I'm relearning mathematics by reading through What is Mathematics?. It begins by explaining the natural numbers, introducing the following property: $a.0=0$ To make $a$ the subject, I would divide ...
3
votes
3answers
122 views

Solve the following equation in positive integers $x$ and $y$

What are the solutions in positive integers of the equation: $${1+2^x+2^{2x+1}=y^2}$$ I tried to factorize the equation but it didn't help much. Clearly $y $ is an odd integer. Substituting $y ...
1
vote
0answers
129 views

How can we prove that this equation cannot be solved?

How can we prove that this equation cannot be solved? $ 25k^3+30k^2+23k+3=x^2$ where x,k are integer numbers
-3
votes
1answer
124 views

The equation $X^{n} + Y^{n} = Z^{n}$ , where $ n \geq 3$ is a natural number, has no solutions at all where $X,Y,Z$ are intergers.

The equation $X^{n} + Y^{n} = Z^{n}$ , where $n \geq 3$ is a natural number, has no solutions at all where $X,Y,Z$ are integers. My solution: False. Because if we let $X=0 ...
1
vote
3answers
78 views

Factorisation of numbers sum with exponent $12$

How can I prove that $n^{12}+64$ has at least four distinct factors other than $1$ and itself? I applied $a^3+b^3$ identity.
2
votes
1answer
548 views

Proof of existence of primitive roots

In my book (Elementary Number Theory, Stillwell), exercise 3.9.1 asks to give an alternative proof of the existence of a primitive root for any prime. Let $p$ be prime, and consider the group ...
2
votes
1answer
52 views

Volume of a parallelepiped

Suppose $\Lambda$ is a lattice in $\mathbb{R}^n$ of rank $r$ and $\mathbf{b}_1, ..., \mathbf{b}_r \subseteq \mathbb{R}^n$ its basis. I know that if we pick any orthonormal vectors $\mathbf{e}_{r+1}, ...
0
votes
1answer
45 views

(a*b*c*…)%C1=C2, How to get random valid solution

This algorithm is made to verify serial numbers. For example: $$3\cdot6\cdot2\cdot9\cdot5\cdot5\cdot6 \bmod 32 \equiv 24$$ $32$ and $24$ are given, and now I need to generate valid numbers for the ...
2
votes
1answer
84 views

How to calculate “gcd product” $\operatorname{gcdp}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$

Given two numbers $m$ and $n$ how can we calculate the gcd product of any two numbers i.e, $\operatorname{gcd p}(n,m)=\gcd(n,1)\gcd(n,2)\cdots\gcd(n,m)$ where gcd is the greatest common divisor? Can ...
2
votes
0answers
106 views

Number Theory easy question.

Prove that $3^{4^{5}} + 4^{5^{6}}$ is the product of two integers greater than $10^{2002}$. A friend already gave me a solution: But I don't really see the motivation behind that. Can somebody tell ...
1
vote
1answer
667 views

proof of commutativity of multiplication for natural numbers using Peano's axiom

How do you prove commutativity of multiplication using peano's axioms.I know we have to use induction and I have already proved n*1=1*n.But I cant think of how to prove the inductive step.
2
votes
1answer
91 views

Find $\sum\frac{a(n)}{n(n+1)}$, where $a(n)$ — number of 1's in binary expansion of n. [duplicate]

Let $a(n)$ is a number of 1's in binary expansion of n, find the sum $$ \sum\limits_{n=1}^{\infty}\frac{a(n)}{n(n+1)}. $$
8
votes
2answers
258 views

Sum of these quotient can not be integer

Suppose $a$ and $b$ are positive integers such that are relatively prime (i.e., $\gcd(a,b)=1$). Prove that, for all $n\in \mathbb{N}$, the sum $$ ...
1
vote
2answers
167 views

Is it sufficient for a number to be a prime if it is not divisible by prime numbers smaller than it?

I am student of computer science with no knowledge of maths. To write a small algorithm I searched for the solution first. There are many but almost all of them state that continue dividing the number ...
1
vote
1answer
85 views

Exercise in algebra with modulo

I'm studying Cassels' book Elliptic Curves for a week now, and I'm at the local global principle. I'm trying to prove the first exercise of this chapter, which says Let $p > 2$ be prime and ...
0
votes
1answer
32 views

Does $p/q$ has at most $n-1$ zeros after a non zero number in its decimal expansion

Is the following true? Let $p$ and $q$ be integers and let $q$ be an integer with $n$ digits, then $p/q$ has at most $n-1$ zeros after a non zero number in its decimal expansion.
6
votes
2answers
108 views

Find the 1000th digit of $N=61218243036\ldots$

If all the multiples of 6 are written side-by-side, then a large integer $N$ is generated as follows: $$N=61218243036\ldots$$ The question is to find the $1000$th digit of $N$. Please simply give a ...
0
votes
3answers
83 views

Let $a,m,n \in \mathbf{N}$. Show that if $\gcd(m,n)=1$, then $\gcd(a,mn)=\gcd(a,m)\cdot\gcd(a,n)$.

Let $a,m,n\in\mathbf{N}$. Show that if $\gcd(m,n)=1$, then $\gcd(a,mn)=\gcd(a,m)\cdot\gcd(a,n)$. Proof: Let $u,v\in\mathbf{Z}$ such that $\gcd(m,n)=um+vn=1$. Let $b,c\in\mathbf{Z}$ such that ...
3
votes
2answers
68 views

What is the number of ways of expressing $120$ as a difference of two perfect squares?

I started this as follows. $120 = a^2 - b^2 = (a+b)(a-b)$ After doing a lot of hit and trial I can come with the answer but that takes time. Is there any other quick way to solve this?
11
votes
3answers
240 views

If $a^4+b^4\in\mathbb Q$ and $a^3+b^3\in\mathbb Q$ and $a^2+b^2\in\mathbb Q$, prove that $a+b\in\mathbb Q$ and $ab\in\mathbb Q$.

If $\begin{cases}a^4+b^4\in\mathbb Q\\ a^3+b^3\in\mathbb Q\\ a^2+b^2\in\mathbb Q\end{cases}$, prove that $a+b\in\mathbb Q$ and $ab\in\mathbb Q$. It is given that $a,b\in\mathbb R$. The proof of ...
0
votes
0answers
32 views

Why does this theorem provide a neccesary and sufficient condition for a $2 \times 2$ linear system of congruences to have a unique solution?

Why does the following theorem both provide a neccesary and sufficient condition for a $2 \times 2$ linear system of congruences to have a unique solution ? I see that $\gcd((ad-bc),m) = 1$ is a ...