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

learn more… | top users | synonyms (1)

0
votes
1answer
12 views

How can we find all solutions to a Pell-type equation?

Is it true that for solveable Pell-type equations, all solutions are given by: 1: Finding fundamental solution to Pell's equation 2: Find all solutions of the Pell-type equation less then the ...
0
votes
0answers
19 views

Proving $\{x| x=km \space\text{for all}\space k∈Z\} = Ø$

I wrote a proof for Let $m$ be any fixed positive integer. $\{x| x=km \space\text{for all}\space k∈Z\} = Ø$, using reductio absurdum. But I'm not sure about the part where $\exists x$ is. Is the ...
0
votes
0answers
17 views

Implication of Inequality

In a step by step breakdown of how to approach Show that $x^4 -py^4 = 1$ has only finitely many integer solutions for $x,y$, where $p$ is a prime number. I don't understand why we can take ...
1
vote
1answer
34 views

When is a prime $p$ a quadratic residue modulo $3$?

Simple. When $p \equiv 1 \pmod 3$, it is a quadratic residue, and when $p \equiv -1 \pmod 3$ it is not a residue. So can we have a nice expression for the Legendre symbol $\left(\frac{p}{3}\right)$? ...
2
votes
2answers
29 views

Difference of subsets of integers with $A-A=2 \mathbb{Z}\setminus \{-2k,2k\}$

Is there any subset $A$ of integers such that $A-A= 2\mathbb{Z}\setminus \{-2k,2k\}$, for some integer $k$? ($A-A=\{a_1-a_2: a_1,a_2\in A\}$, and $2\mathbb{Z}$ is the set of even integers.)
1
vote
1answer
39 views

doesn't exist an $N$ s.t. all $n \ge N$ satisfy an equation.

I came across this problem on my own and i'm asking for any potential techniques/strategies/hints for attacking it. Prove that there does not exist an $N$ such that for every natural number $n ...
1
vote
5answers
52 views

Prove that if $n$ is not divisible by $3$, then $n^2 \equiv 1 \pmod 3$

I can see that it is true for all cases where $n$ is not divisible by $3$, such as $n = 1$, $n = 2$, $n = 4$, etc. However I cant figure out how to prove it.
2
votes
1answer
45 views

Solve $\begin{cases}x\equiv 1\pmod{5}\\x\equiv0\pmod{66}\\x\equiv6\pmod 7\end{cases}$

Solve $$\begin{cases} x\equiv 1\pmod{5}\,\,\,\qquad\qquad.1\\ x\equiv0\pmod{66}\qquad\qquad.2\\ x\equiv6\pmod 7\,\,\,\qquad\qquad.3 \end{cases}$$ My attempt: $\gcd(66,5,7)=1$ so I can apply the ...
1
vote
1answer
68 views

Given $x_m=4x_{m-1}-x_{m-2},\ x_1=1,\ x_2=3$

I friend told me that apart from trivial ones, the elements in this sequence never equal powers of 3: $$x_m=4x_{m-1}-x_{m-2},\ x_1=1,\ x_2=3.$$ Could you please help me to prove this?
0
votes
0answers
10 views

To find out HCF of two numbers [duplicate]

Given that $(a,b)=1\ \text{and}\ p\ \text{is odd prime,then prove that }(a+b,\frac{a^p+b^p}{a+b})\ \text {is 1 or}\ p$. have no idea where to start.any hint please
0
votes
2answers
15 views

Prove that if $\gcd(b, c) = 1$, then $\gcd(a, bc) = gcd(a, b) * gcd(a, c)$. [on hold]

I am stumped in this problem. Could anybody please clarify why that is true?
0
votes
1answer
17 views

Prove if d | mn when gcd(m, n) = 1 , then gcd(d, mn) = d. [on hold]

This seems pretty obvious to me, but I'm having hard time coming with a proof. Could you please help me?
0
votes
1answer
15 views

Proving that if gcd(m, n) = 1, and if d divides mn, then there exist unique numbers a and b such that a divides m, b divides n, and d = ab.

What do I know? If d | mn, there exist an integer k such that dk = mn. I also know that because gcd(m, n) = 1 there exist some integers x and y such that mx + ny = 1. I am having trouble to prove ...
3
votes
0answers
42 views

Need help bounding Merten's function for large x

Recall that Merten's function is defined as: $$M(x) = \sum_{n\le x}\mu(n)$$ Using the following prime counting functions to represent the count of integers less than $x$ with $k$ prime divisors: ...
2
votes
3answers
33 views

What are the differences between these two statements?

For every positive real number x, there is a positive real number y less than x with the property that for all positive real numbers z, yz ≥ z. For every positive real number x, there is a positive ...
2
votes
0answers
27 views

A congruence of sum of kth powers of first p-1 numbers [duplicate]

Problem: For $k < p-1$ where $p$ is an odd prime and $k$ is a natural number, prove that $$1^k+2^k+\cdots+(p-1)^k \equiv 0 \mod p.$$ My attempt: It's obvious for odd $k$, as we can pair the ...
-1
votes
1answer
35 views

Meta-Pythagorean Triple

How can I find all Pythagorean triples $(a,b,c)$ such that the hypotenuse $c$ is a leg in another Pythagorean triple? For example, $(3,4,5)$ is such a Pythagorean triple because the length of the ...
2
votes
0answers
41 views

show quadratic forms $x^2 + y^2 + z^2$ and $ x^2 - y^2 - z^2$ are equivalent over finite fields $\mathbb{F}_p$

Can I show the diagonal matrix (1,1,1) and (1,-1,-1) are equivalent over the finite field $\mathbb{F}_3$ Can I show the quadratic forms $x^2 + y^2 + z^2$ and $x^2 - y^2 - z^2$ are equivalent over the ...
0
votes
0answers
25 views

Number of solutions of a difference-of-two-squares congruence with prime moduli

Problem: Show that if $p$ is an odd prime then $p-1$ number of ordered pairs $x, y$(unique modulo p) satisfy $x^2-y^2 \equiv a\mod p$ (for some given $a$ coprime to p). When $a \equiv 0 \mod p$ then ...
4
votes
2answers
65 views

Show $\frac{2}{\sqrt[3]2}-\frac{1}{2(\sqrt[3]2-1)}+\left(\frac{9}{2\sqrt[3]4}-\frac{9}{4}\right)^{\frac{1}{3}}=\frac{1}{2}$?

Prove that: $$\frac{2}{\sqrt[3]2}-\frac{1}{2(\sqrt[3]2-1)}+\left(\frac{9}{2\sqrt[3]4}-\frac{9}{4}\right)^{\frac{1}{3}}=\frac{1}{2}$$ The LHS is irrational number and RHS is rational number. May be ...
1
vote
2answers
66 views

Prove that $(√5 - 1)/2$ is irrational.

Please help me prove that $(√5 - 1)/2$ is irrational. I know how to prove √5 is irrational: Assume that √5 is rational meaning √5 = $p/q$ $p,q$ $are$ $Z$ $and$ $q≠0$ $p^2/q^2 = 5$ $q^2 = ...
1
vote
0answers
39 views

What is the largest integer $k$ such that $4^{k} \vert 100!$?

What is the largest integer $k$ such that $4^k \vert 100!$. I understand the case where you have a composite number $n^k \vert 100!$ (where $n$ has two or more distinct primes), but I'm getting a ...
2
votes
1answer
47 views

Solve $\begin{cases}x\equiv-4\pmod {17}\\ x\equiv 3\pmod{23} \end{cases}$

Solve $$\begin{cases}x\equiv-4\pmod {17}\\ x\equiv 3\pmod{23} \end{cases}$$ My attempt: $$\gcd (17,23)=1$$ so using the Chinese remainder theorem there is a solution modulo $17\times 23=391$ ...
0
votes
2answers
61 views

Number of positive integer solutions to the equation $(a+b+c)(x+y+z+w) = 15$ [on hold]

What is the total number of positive integer solutions to the equation? $$(a+b+c)(x+y+z+w) = 15$$ I could not find a way to solve this algebraically. The way which all other answers are telling i ...
6
votes
3answers
607 views

Find the remainder when a large number is divided by 35.

I don't know why I am wrong with this problem. Here is what I did: The last two digit of $6^{2006}$ is 36. So the answer should be 1. Find the remainder when $6^{2006}$ is divided by 35.
0
votes
0answers
16 views

Number of roots of quadratic polynomial in $ Z/(pq Z) $

I want to prove that quadratic polynomials in $ Z/(pq Z)$ have at most 4 roots, when $ p, q $ are prime. I currently do this by factoring the polynomial, $(x-a)(x-b) $ and then showing that either x ...
2
votes
2answers
46 views

To show that the variables in the system are same in magnitude

I am stuck with this interesting problem, If for non-negative integers $a, b, \text{and} c$, $\frac{a}{b}+\frac{b}{c}+\frac{c}{a}$ and $\frac{b}{a}+\frac{c}{b}+\frac{a}{c}$ are both integers then ...
2
votes
2answers
36 views

Show that for any $a,b\in\mathbb{Z}$, $p$ prime: $(a^p+b^p)^{p^2}\equiv a+b \pmod p$

Show that for any $a,b\in\mathbb{Z}$, $p$ prime: $$(a^p+b^p)^{p^2}\equiv a+b \pmod p$$ Using the binomial expansion, I found that ...
1
vote
3answers
33 views

Show that if $a$ is an integer, $(a^2-a)/2$ is an integer too.

Please help me on this number theory problem. Show that $a\in\mathbb Z$, then $\frac{a^2-a}{2}\in\mathbb Z$.
0
votes
1answer
37 views

Exponential equation possibly with congruences and number theory

$3^x+5^y=a^2$ ($x, y, a$ are non-negative integers) Find all pairs $(x, y)$ which satisfy the equation. I have found the trivial solution $x=1, y=0$, and I have tried with congruences, but it didn't ...
-1
votes
1answer
77 views

Is there a sequence of positive integers such that $a_{n+3}-a_{n+2}=\sqrt{a_{n+1}+a_n}$? [on hold]

Can anyone give me a hint on this? Is there a sequence of positive integers such that $(a_{n+3}-a_{n+2})^2=a_{n+1}+a_n$ for all $n$? Or strongly, $a_{n+3}-a_{n+2}=\sqrt{a_{n+1}+a_n}$. If there is, ...
2
votes
2answers
61 views

Prove $1+\frac{1}{\sqrt{\phi^{4n+1}{F_{2n}F_{2n+1}}}+\phi^{2n+1}F_{2n}}=\sqrt{\frac{F_{2n+1}}{\phi{F_{2n}}}}$

$n \ge 1$ $F_n$; Fibonacci numbers $\frac{1+\sqrt5}{2}=\phi$ Prove $$1+\frac{1}{\sqrt{\phi^{4n+1}{F_{2n}F_{2n+1}}}+\phi^{2n+1}F_{2n}}=\sqrt{\frac{F_{2n+1}}{\phi{F_{2n}}}}$$ I can't go any further ...
1
vote
3answers
61 views

Show that if $n\equiv 3, 6 \pmod9 $ then $n$ is not a sum of two squares

Show that if $n\equiv 3, 6 \pmod9 $ then $n$ is not a sum of two squares. I started by: Assume $n=a^2+b^2$ a sum of two squares. Then $a^2,b^2\equiv 0,1,4,7 \pmod9$, and no combination these numbers ...
0
votes
0answers
32 views

Number theory/calculus/algebra etc. equivalents of Euclid's Elements?

Anybody know any books that tackle mathematical topics in a deductive, axiomatic structure akin to Euclid's Elements? Thanks.
0
votes
1answer
11 views

Solving Modular Equations in ${Z_{18}}$ Given Inverses…

I need to solve equations like $5X\bmod 18 = 11$ in ${Z_{18}}$ given their inverses. (The modular multiplicative inverse of 5 being 13 in this case.) How would I do that?
1
vote
0answers
24 views

$p \in \Bbb P, a \in \Bbb N$, then if $ord_p(a)=d$ we have $a^{d-1}+\dots+a+1 \equiv 0 \mod p$.

I want to prove the statement in the title, but I think we need $d \geq 2$ in the statement since otherwise there is a case not fulfilling the statement. My attempt: By assumption we have ...
0
votes
1answer
31 views

Diophantine Equations… $255x + 345y = 60$.

I need to know how to find the general solution by integers to any equation (or identify when there is no such integer solution). The example in my mock exam is $255x + 345y = 60$. I think you need ...
1
vote
2answers
39 views

Elementary Number Theory: Chinese Remainder Theorem

Using the facts that $1591=37.43$ and $51=3.17$ compute 1591 mod 51 using the Chinese Remainder Theorem. I started off by letting $x \equiv 1591 \mod 51$ which I then wrote as $x \equiv 1591 \mod ...
1
vote
2answers
37 views

Finding Modular Multiplicative Inverses (Quickly!)

as part of an upcoming number theory exam I will need to find the modular multiplicative inverse of every element of ${Z_n}$ (the ones that exist anyway) very quickly. The only way I know is using the ...
10
votes
4answers
135 views

Prove that $2^n+3^n $ is never a perfect square

My attempt : If $n$ is odd, then the square must be 2 (mod 3), which is not possible. Hence $n =2m$ $2^{2m}+3^{2m}=(2^m+a)^2$ $a^2+2^{m+1}a=3^{2m}$ $a (a+2^{m+1})=3^{2m} $ By fundamental ...
3
votes
0answers
55 views

Partitioning positive integers using digital rivers

I stumbled on a very simple computer science question from the British Informatics Olympiad for schools and colleges. Embedded in it is a very interesting numbers theory problem. Here is the ...
0
votes
1answer
16 views

A certain number when successively divided by $8$ and $11$ leaves remainders of $3$ and $7$, respectively.

A certain number when successively divided by $8$ and $11$ leaves remainders of $3$ and $7$, respectively. What will be the remainder when the number is divided by the product of $8$ and $11$, $88$?
1
vote
1answer
44 views

What the sign ' | ' stand for?

Going through a proof of a theorem, I encountered the following statement: $e\mid a/d$, $e\mid b/d$ Then, $a/d = ex$, $b/d = ey$ where $x,y$ belongs to $\mathbb{Z}$. However, my question ...
6
votes
0answers
143 views

Seemingly easy Diophantine equation $a^3+a+1=3^b$

How to prove that $a=b=1$ is the only positive integer solution to the following Diophantine equation?$$a^3+a+1=3^b$$
3
votes
1answer
57 views

How to compute $(1 \cdot 3 \cdot 5 \cdots 97)^2 \pmod {101}$ [on hold]

How to compute $(1 \cdot 3 \cdot 5 \cdots 97)^2 \pmod {101}$ in easiest and fastest way?
1
vote
2answers
30 views

Total number of perfect square which are factors of n [on hold]

A number $N$ can be factorized as $$N = p_1^5 p_2^4 p_3^7.$$ Find total number of perfect square, which are factors of $N$.
4
votes
1answer
29 views

On the GCD of two palindromes.

I had an observation. Which I will discuss below. My question will be Is my observation correct? If so, how can one prove it? Observation: Consider the string of palindromes below: $100...01$ and ...
1
vote
1answer
47 views

Do primes “behave” in this way?

Suppose that we choose some real number $\varepsilon >0$. Can we always find $n_0(\varepsilon) \in \mathbb N$ such that for every $n> n_0(\varepsilon)$ there is a prime number $p$ such that ...
0
votes
0answers
56 views

How do I make this formula for the primes more concise?

The form I made for the $(n+1)^{th}$ prime $p_{n+1}$ is $\displaystyle1+\sum_{j=1}^{2p_n-1}\lfloor\frac{p_n!^j}{j!}\rfloor-\lfloor\frac{p_n!^j-1}{j!}\rfloor=p_{n+1}.$ Problem is, just like any ...
0
votes
1answer
24 views

Ιnequality relationship

Let $a,b,c,d$ positive numbers. They are connected with the relations $$b<d,\quad a<c,\quad b<a,\quad d<c$$ Is it possible to prove that $a-b<c-d$?