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

learn more… | top users | synonyms (1)

4
votes
2answers
50 views

Interesting and unusual word problem with prime numbers and factors

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with prime numbers, but other than that, the textbook gave no hints really and ...
7
votes
5answers
154 views

Which one is bigger: $9^{17}$ and $7^{19}$

One friend asked me to find which one is bigger: $9^{17}$ and $7^{19}$ using basic calculations only. I gave him a solution by using the technique given in here. However, it was not that basic since I ...
2
votes
1answer
16 views

Meaning of HCF in a problem sum

When a group of children shared a box of 200 beads equally , there were 4 beads left . When the remaining heads were added to another box of 80 beads and shared equally , there were no beads left. ...
0
votes
2answers
13 views

Proof about composed functions

Let $f\colon X \to Y$ and $g\colon Y \to X$ be functions. Assume $g \circ f$ is bijective. Prove $f$ is injective and $g$ is surjective. Approach: if $g \circ f$ is bijective then $g \circ ...
2
votes
2answers
132 views

$ 1^k+2^k+3^k+…+(p-1)^k $ always a multiple of $p$?

I would appreciate if somebody could help me with the following problem: Q: For any prime number $p(p\geq 3), k=1,2,3,...,p-2$, why is $$ 1^k+2^k+3^k+...+(p-1)^k $$ always a multiple of $p$ ?
0
votes
3answers
20 views

LCM HCF (factors)

A number has exactly six factors , two of the factors are 9 and 15. List all the factors of the number . First I found LCM of 9 and 15, and then I'm stuck and not sure how to carry on.. Can I get a ...
0
votes
1answer
21 views

Find the number of such $4$-tuples $(a,b,c,d)$

If $a \in\{1,2\}$, $b \in\{1,2,4\}$, $c\in\{1,2,3,6\}$ and $d\in\{1,2,4\}$.Find the number of $4$-tuples $(a,b,c,d)$ such that lcm$(a,b,c,d)=12$.
1
vote
0answers
26 views

Prove that $\sum_{j=0}^{n}H_j{n\choose j}^2={2n\choose n}\left(2H_n-H_{2n}\right)$

$H_n$ ; Harmonic numbers $H_0=0$ Prove that, $$\sum_{j=0}^{n}H_j{n\choose j}^2={2n\choose n}\left(2H_n-H_{2n}\right)$$ I encounter this problem since 2012 and have verify numerically and not sure ...
0
votes
1answer
17 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 ...
2
votes
2answers
164 views

Is there $\phi(n)=n/6$

I know how to find for which $n$ $\phi(n)=n/2$ or $\phi(n)=n/3$, my method for finding those was simply to find primes $p$ that satisfy $\Pi_p$$_|$$_n$$1-1/p$ $ = 1/2$ or $1/3$. However, I don't ...
0
votes
0answers
21 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 ...
6
votes
0answers
151 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$$
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
0answers
40 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
0answers
43 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 ...
2
votes
2answers
32 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
40 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
1answer
71 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?
3
votes
0answers
44 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: ...
4
votes
1answer
80 views

Number of nonnegative integral solutions of $ x_1 + x_2 + x_3 +\cdots + x_m = k $

What I'm tyring to show is the number of solutions to the equation of natural numbers; $$ x_1 + x_2 + x_3 +\cdots + x_m = k $$ is equal to $$ \binom{m + k - 1} m $$ To be blunt, I have no idea ...
1
vote
5answers
57 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
49 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 ...
0
votes
1answer
18 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 ...
0
votes
2answers
16 views
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
1answer
18 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?
2
votes
3answers
34 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 ...
0
votes
2answers
2k views

Proof — Infinitely many primes of the form $4k + 3$ — origin of $4(p_1…p_k - 1) + 3$

I know there are sundry questions — like this pdf — and this (10.) Prove that any positive integer of the form $4k + 3$ must have a prime factor of the same form. Because $4k + 3 = 2(2k + 1) + 1$, ...
-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 ...
0
votes
0answers
26 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 ...
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 ...
3
votes
1answer
114 views

Factors of the numbers of the form $a^2+nb^2$

Let $N=a^2+nb^2$ with $\gcd(a,b) =1$ and $n \in \mathbb{Z^+}$. If $N=xy$ where $x$ and $y$ are relatively prime numbers, in what condition can $x$ and $y$ be also written in the same form as $N$ ...
4
votes
2answers
66 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 ...
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 ...
7
votes
3answers
539 views

Is the digital root of twin primes product larger than (3,5) always 8

Is the digital root of twin primes product larger than $(3,5)$ always $8$? E.g. I just checked the following and it is true was wondering if it is more widely true $5\times 7=35$, digital root ...
6
votes
3answers
608 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
1answer
166 views

Number of trailing zeros at other bases

Q. $85!$ ends with exactly $20$ trailing zeros. When $85!$ is converted to base $N$, $N$ being any natural number, it so happens that it has the same number of zeros at the end. What could be the ...
3
votes
3answers
464 views

How many sets of two factors of 360 are coprime to each other?

My attempt: $360=2^3\cdot3^2\cdot5^1$ Number of sets of two factor coprime sets for $2^3$ and $3^2$ only $=12+6=18$ With that if we add the effect of $ 5^1$, number of sets $=18+2\cdot 18-1=53$. ...
2
votes
2answers
70 views

Odd binomial sum equality has only trivial solution?

Suppose $$\sum_{k\ {\rm odd}}^n {n \choose k} 2^{(k-1)/2} = \sum_{k\ {\rm odd}}^m {m \choose k} 2^{(k-1)/2} 3^{(m-k)/2}.$$ Does $m=n=1$? Clearly $m \leq n$, and for every $n$ there is at most one ...
1
vote
2answers
69 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 = ...
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$ ...
1
vote
0answers
42 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
2answers
47 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 ...
-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, ...
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
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$.
2
votes
1answer
1k views

How to solve difficult positive integers and co-prime word problem?

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with derivative of algebra and prime numbers, which yields the shortest, ...
3
votes
4answers
112 views

Proof that $3 \mid \left( a^2+b^2 \right)$ iff $3 \mid \gcd \left( a,b\right)$

After a lot of messing around today I curiously observed that $a^2+b^2$ is only divisible by 3 when both $a$ and $b$ contain factors of 3. I am trying to prove it without using modular arithmetic ...
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 ...