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

learn more… | top users | synonyms (1)

-2
votes
2answers
81 views

How to check if $2$ is a square $\mod 3$?

I don't think I can use the Legendre or Jacobi symbol here because $2$ is an even prime. I'm not sure I've learned methods to deal with $2$ even though I know how to use quadratic reciprocity, it only ...
2
votes
0answers
23 views

$r$ is a primitive root of odd prime $p$ and $a\not\equiv 0\pmod{p}$. Find the number of solutions to the congruence $xr^x\equiv a\pmod{p}$

$r$ is a primitive root of odd prime $p$ and $a\not\equiv 0\pmod{p}$. Find the number of solutions to the congruence $$xr^x\equiv a\pmod{p}$$ Here is my attempt : Since $r$ is a primitive root, ...
3
votes
5answers
69 views

If $a,b,c$ are integers such that $4a^3+2b^3+c^3=6abc$, is $a=b=c=0$?

If $a,b,c$ are integers such that $4a^3+2b^3+c^3=6abc$ , then is it true that $a=b=c=0$ ? I was thinking of infinite descent but can't actually proceed , please help. Thanks in advance
0
votes
0answers
29 views

Big $O$ notation and computations

Here all the functions of natural numbers are positive.$p$ is a prime number. Let $A(n)+B(n)=C(n)+D(n)$ where $B(n)=O(p^{5n})$. $ A(n)$ is always less that or equal to $C(n)$.$D(n)$ is known to be of ...
0
votes
1answer
68 views

Find the least positive integer with $24$ positive divisors.

Find the least positive integer with $24$ positive divisors. My attempt: $24=2^3.3$. We shall have to find out a positive integer (least) $n$ such that $N$ has $24$ positive divisors i.e we have ...
3
votes
2answers
56 views

The diophantine equation $x^2+y^2=3z^2$

I tried to solve this question but without success: Find all the integer solutions of the equation: $x^2+y^2=3z^2$ I know that if the sum of two squares is divided by $3$ then the two numbers ...
2
votes
1answer
36 views

There exists a number expressible as the sum of $2015$ $2014$th powers in at least two ways

Prove that there exists a positive integer that can be written as the sum of $2015$ $2014$th powers of distinct positive integers $x_1 <x_2 <\ldots <x_{2015}$ in at least two ways. How can I ...
1
vote
2answers
36 views

Proof that $(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$ [duplicate]

$(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$ my work: I assumed m = da , n = db for a,b $\in$ Z. Now, $2^m - 1$ = $2^{da} - 1$ = $(2^d)^a - 1$ = $x^a - 1$ where $x = 2^d$. similarly $2^n - 1$ = ...
-1
votes
1answer
46 views

find a formula for $S(n)$ [closed]

Let $S(n) =\sum\tau(d)\sigma^2(d)$, where the sum is taken over all divisors $d$ of $n$. How to find a formula for $S(n)$ in terms of the prime factorization of $n$?
1
vote
1answer
31 views

Determining prime numbers p which satisfy quadratic residues modulo p

I'm learning about quadratic reciprocity and I'm stuck on an exercise. It states : Determine the congruence characterizing all prime numbers p for the following integers such that they are quadratic ...
0
votes
1answer
59 views

Greatest integer which divides $2001\times\ 2002\times 2003\times\ \cdots\times\ 2009$

Here i have a problem. Find the greatest integer which divides $2001\times\ 2002\times 2003\times\ \cdots\times\ 2009$. I couldn't get the problem actually, how to start with?
1
vote
1answer
23 views

Proof on the Legendre Symbol

I'm working on an exercise involving the Legendre Symbol. It gives me a hint but I'm not sure how to prove it. Let p and q be odd prime numbers with $p = q + 4a$ for some $a \in \mathbb{Z}$. Prove ...
0
votes
0answers
18 views

Estimating the number of integers in a sequence of consecutive integers that are relatively prime to a given primorial

Let $x,y$ be positive integers and $p$ a prime. Is there a standard way to estimate the number of integers $z$ where $x \le z < x+y$ and $\gcd(z,p\#)=1$ For example, for $x=1000, y=30, p=7$, ...
1
vote
3answers
33 views

Determining maximum possible number of pieces of a bar with given number of cuts

I came across a challenge on Hackerrank which has me stumped literally. It is a coding problem but I am not looking for the code, rather I can't figure out the mathematical approach towards it. ...
1
vote
0answers
19 views

Condition for an integer prime to be a Gaussian prime

I have a basic question: To show that an integer prime $p$ is a Gaussian prime (i.e. a prime in the ring of Gaussian integers $\mathbb Z[i]$) if and only if the equation $x^2+y^2=p$ has no integer ...
0
votes
4answers
52 views

$b|a$ and a|b then $a=b$ help

I am stuck on this really simple proof. $b|a$ and a|b then $a=b$, where a,b are positive. I tried to right a=bk and b=am and do something with that but am getting stuck.
5
votes
8answers
284 views

If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
0
votes
0answers
23 views

Number of operation to transform $(0,0,0)$ to $(a,b,c)$ with $2^h\leq a,b,c \leq 2^h-1$

Given a positive integer $h$, define: $$A_h=[2^h,2^{h}-1]\big \{2^h-1+\sum_{i\in A}2^i \Big/ A\subset[0,h-1]\big \}$$ (this is in terms of binary expressions: the set of all numbers having exactly $h$ ...
3
votes
0answers
89 views

To prove $\phi(mn)\phi(d)=\phi(m)\phi(n)d$ without explicitly computing the phi function values

If $m,n$ are positive integers with g.c.d.$(m,n)=d$ , then we can show by explicitly computing respective totients that $\phi(mn)\phi(d)=\phi(m)\phi(n)d$, I want to know, is there any more elegant way ...
1
vote
2answers
39 views

Show that the sum of the products in pairs of the number 1,2,3…p-1 is divisible by p, where p is prime

If $p ≥ 5$ is prime, show that the sum of the products in pairs of the numbers $1, 2, . . . , p−1$ is divisble by p. We do not count $1×1$, and $1 × 2$ precludes $2 × 1$.
0
votes
1answer
13 views

Possible dividers of a number of three digits

For each natural number n of 3 decimal digits (thus with the first non-zero digit), we consider the number n0 n obtained by eliminating its possible digit equal to zero. For example, if n = 205 then ...
2
votes
1answer
40 views

Last Digits of a Tetration

I was studying tetrations, or "power towers", and I found a decently well-known fact. The last $k-1$ digits of $^k 3 = 3^{3^{\vdots^{3}}} (k \text{ threes)}$ remain constant, for all numbers $^a 3$ ...
1
vote
1answer
36 views

($G$ is abelian) if $gcd(|x|,|y|) = 1$ then $|xy| = lcm(|x|,|y|)$

I am trying to prove this my idea was we have the following $|x||y| = lcm(|x|,|y|)\times gcd(|x|,|y|)$ since we have $gcd(|x|,|y|) = 1$ $|x||y| = lcm(|x|,|y|)$ Suppose that $|x| = n $, $|y| = m$ , ...
2
votes
5answers
116 views

Find all solutions $a,\ b\in \mathbb{ N}$ to the equation $2^a = b^ 2 − 5$ [duplicate]

How would on earth, anyone can prove this. frustrated! Please help.
0
votes
1answer
45 views

Duplicated Number Perfect Squares [closed]

For which numbers $N$ is the number $10^k \cdot N + N$, where $k$ is $N$'s length, a perfect square?
1
vote
2answers
22 views

Prove $d = \gcd(a,b) \iff 1= \gcd (k_1, k_2)$. [duplicate]

This is the assumption they give me: Let $a, b$ be integers and $d$ a positive integer. Let $d|a$ and $d|b$ so there there exists $a=dk_1$ and $b=dk_2$. I can go the backwards direction but I'm ...
7
votes
0answers
93 views

Let $p$=prime and $\sqrt{x}+\sqrt{y}<\sqrt{2p}$

Let $p$ be a fixed odd prime. Let $x,y\in \mathbb{Z}_+$ such that $\sqrt{x}+\sqrt{y}<\sqrt{2p}$. Prove that $$\sqrt{x}+\sqrt{y}\le \sqrt{\frac{p-1}{2}}+\sqrt{\frac{p+1}{2}}.$$ Any ideas at all? ...
0
votes
0answers
37 views

Rational And Real Numbers Density

I know that $\mathbb{Q}$ and $\mathbb{R}$ are dense and that there cardinalities are $\aleph_0$ and $\aleph$ corresponding. Does from these facts I can assume that any interval of $\mathbb{Q}$ or ...
1
vote
0answers
29 views

Diophantine linear Equation Gaussian Integers

We know that $ax+by=c$ with $gcd(a,b)=1$ could be solved over $\Bbb Z$. Supposing if $a,b,c\in\Bbb Z[i]$, is there an analogous framework to find $x,y\in\Bbb Z[i]$ (at least of minimum norms)?
0
votes
1answer
98 views

On a theorem of Kronecker! [closed]

Let $\alpha$ be an irrational number and $\beta$ be an arbitrary real number, Prove that there are infinitely many pair of integers $(x,y)$ with $x\in\mathbb{N}$ such that: ...
0
votes
1answer
62 views

all elements of ($Z$/p$Z$)* are cubes

Let $p$ be a prime An element $a \in$ ($Z$/p$Z$)* is called a cube if there exists $b \in$ ($Z$/p$Z$)* such that $a = b^3$ How to show that all elements of ($Z$/p$Z$)* are cubes ? And if $p \equiv ...
1
vote
1answer
50 views

Find the sum of the digits of the number

Obviously, $a_1 \ne 0$ and $a_1 \ge 1$. $$N = 10^n a_1 + 10^{n-1} a_2 + \cdots + 10^0 a_n$$ But I dont think I can do a lot more.
6
votes
2answers
52 views

The product of all differences of the possible couples of six given positive integers is divisible by 960.

How can I show that the the product of all differences of the possible couples of six given positive integers is divisible by $960$? $$x_1≥x_2≥x_3≥x_4≥x_5≥x_6$$ $$960\mid (x_1-x_2 )(x_1-x_3 ...
5
votes
1answer
116 views

Denesting a square root: $\sqrt{7 + \sqrt{14}}$

Write: $$\sqrt{7 + \sqrt{14}} = a + b\sqrt{c}$$ Form. $$7 + \sqrt{14} = a^2 + 2ab\sqrt{c} + b^2c$$ $a^2 + b^2c = 7$ and $2ab = 1$, and $c = 14$ But that doesnt seem right as $a, b,$ wont be ...
-1
votes
2answers
63 views

If p is an odd prime then prime divisors of $(2^p-1)$ [duplicate]

If $p$ is an odd prime Prove that the prime divisors of $(2^p-1)$ are of the form $(2rp+1)$.
0
votes
1answer
31 views

Show that $29 | N$ Problem

Let $\frac{29}{25} x_1$ and $\frac{39}{50}x_2$ equal $N$ for some $x_1,x_2$. If $x_{1,2}$ are positive integers show that: $$29 | N,\space \text{and} \space 39 | N$$ So, $$29 | N \implies ...
2
votes
2answers
138 views

$a, b \in\Bbb N$, find all solutions to $2^a = b^2 - 5$ and prove there are no more solutions?

I am currently studying discrete mathematics at uni (in my computer science degree). We have an assignment due tomorrow, and i have been able to do most of it, but one question eludes me. I spoke to a ...
1
vote
2answers
65 views

Form of a prime dividing a certain difference of two prime powers.

Let $p$ and $q$ be odd primes. If $q|(a^p-1)$ then, either $q|(a-1)$ or $q=(2rp+1)$ for some integer $r$.
2
votes
3answers
54 views

Given LCM of three natural numbers, find the possibilities.

LCM of three natural numbers =150. How many sets of three numbers are possible? I know how to do this for two natural numbers.There is also a general formula for that. But for 3 numbers it is posing ...
5
votes
1answer
68 views

Smallest number of primes

Let $P$ be a set of primes, such that for each nonnegative integer $n$, $19⋅8^n+17$ is divisible by some prime $p$ in $P$. Find the smallest possible number of elements in $P$. How do I start the ...
1
vote
0answers
34 views

Let $f(x), g(x) \in C[x]$. Suppose $f(x) | g(x)$ and let $c \in C$. Prove that if $f(c) = 0$ then $g(c) = 0$. Is the converse true?

Let $f(x), g(x) \in C[x]$. Suppose $f(x) | g(x)$ and let $c \in C$. Prove that if $f(c) = 0$ then $g(c) = 0$. Is the converse true? What I have so far: Since $f(x) | g(x)$, $f(x) = g(x)q(x)$ from ...
1
vote
2answers
65 views

From any ten naturals, find some numbers whose sum is divisible by $ 10.$

Consider $A \subset \mathbb N $ such that $|A| = 10.$ Then prove that there exists a non-empty $B \subseteq A$ such that the sum of the elements in $B$ is divisible by $10.$ How to go to the gist ...
0
votes
1answer
49 views

Product of Distinct Primitive roots

Let $p$ be an odd prime. Show that the product of the distinct primitive roots, $\mod{p}$, is $\equiv$ $1$ or $-1$ $\pmod{p}$. I think this can be done by viewing the primitive roots as a elements of ...
0
votes
0answers
37 views

$n^3 + n^2 + n + 1 = m^2$ for positive integers $m$ and $n.$ [duplicate]

How do I prove that $n = 7, m = 20$ and $n = 1, m = 2$ are the only solutions to this? I don't think it can be proved that it always lies between $2$ squares for all numbers other than $1$ and $7.$
7
votes
2answers
152 views

Solve $x^3=y^2-y+1$ in positive integers.

I recently started doing number theory and have finished with all the basic, intermediate and some of the advanced stuff with ease. However, I encountered this question and have been stuck for about a ...
-1
votes
0answers
29 views

GCD and remainders

Can anyone please help me with a problem associated to GCD. Say we have 2 numbers 30 and 42. What is the largest integer which when divides these two numbers will produce the same remainder? The ...
3
votes
1answer
50 views

Prove that for all naturals $n \ge 6$ there is a set of $n$ positive naturals, $a_1$ to $a_n$ such that $\sum_{i=1}^n \left(\frac{1}{a_i}\right)^2 =1$

I don't know how to prove this. I know that $\{2, 2, 2, 2\}$ is a set for $n = 4$, since $\left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 + ...
1
vote
2answers
71 views

Prove if, $2^n - 1$ is prime, then $n$ is prime. [duplicate]

Prove, when $n$ is a positive integer, if $2^n - 1$ is prime, then $n$ is prime. I did read some sort of proving on the web, but I could not understand it... Any help? And if possible, could the ...
3
votes
1answer
23 views

In $\mathbb{Z}$, let m~n iff m-n is a multiple of 10.

Prove that each of the following is an equivalence relation on the indicated set. Then describe the partition associated with that equivalence relation. In $\mathbb{Z}$, let m~n iff m-n is a ...
2
votes
1answer
27 views

Proof that $a,r,s$ are odd and $b$ is even

I was trying to do this proof where: Assume $a,b,r,s$ are relatively prime, and that $$a^2+b^2=r^2$$ and $$a^2-b^2=s^2$$ Prove that $a,r,s$ are odd and $b$ is even. So I started off by saying that ...