This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms (1)

-2
votes
1answer
15 views

Example of GCD=1, but… [on hold]

Give an example of three positive integers $m$, $n$, and $r$, and three integers $a$, $b$, and $c$ such that the GCD of $m$, $n$, and $r$ is $1$, but there is no simultaneous solution to: $x ≡ a ...
0
votes
1answer
40 views

Computing $\mathrm{gcd} (100!, 3^{100})$

I am trying to compute $\mathrm{gcd}(100!,3^{100})$. I am still not sure how to reach an answer but I feel that Wilson's Theorem (i.e., $(p-1)!\equiv -1 \bmod p, p$ prime) and Fermat's Little theorem ...
1
vote
4answers
51 views

Show that if $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$.

Show that if $m$ and $n$ are integers such that $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$. I am not sure where to begin.
0
votes
1answer
8 views

Factors of polynomial not passing the Bezout's identity test

When factoring $x^3 - 2x^2 - 4x - 8$ the result you get is $(x-2)(x^2 - 4)$ or $(x-2)^2 (x+2)$ , meaning that the mentioned polynomial is divisible by each of these factors. When using the Bezout's ...
0
votes
2answers
35 views

Proving rigorously that if $3\mid(a+b)$ then $3\mid(a^3+b^3)$ using divisibility definition

Let $a,b\in \mathbb Z$. Prove rigorously using divisibility definition that if $3\mid(a+b)$ then $3\mid(a^3+b^3)$ After a bit of algebra I get that $$3\overset{?}{\mid}(a+b)^3-3ab(a+b)$$ So now how ...
0
votes
4answers
66 views

$\gcd(4n+1, n+2)$ is found in what sense?

What is the gcd of these two numbers? Is it possible to find the gcd? It should be $1$ when $n=1$, but $3$ when $n=5$. $4n+1 = (3)(n+2) + (n-5)$ <-- This step is only valid when $n \geq 5$ How do ...
0
votes
0answers
30 views

Finding how many divisors a number has between two given values

I need to find how many divisors a number has between two given values, including 1 if it is in range, and including both of these values. Let us denote it as D(n,a,b), where n is the number, a is ...
1
vote
2answers
30 views

How to recognise the digit multiplication, subtraction or addition when checking for divisibility by 7, 11, 13, 17 and 19?

I was studying this page Divisibility by prime numbers under 50 to check for the divisibility by 7, 11, 13, 17, 19 etc. Is there any way to recognise whether to add or sub the given times of unit ...
0
votes
0answers
20 views

finding the logic behind the division method of hcf [on hold]

How does the division method of finding hcf work.should we consider that their exist a common factor that divides both the numbers.
2
votes
3answers
122 views

Prove that distinct Fermat Numbers are relatively prime [duplicate]

The Fermat numbers are defined by $F_m = 2^{2^m} + 1$. Prove that for $m \ne n$ we have $(F_m, F_n) = 1$. I have to first prove that $F_{m+1} = F_0F_1 \cdots F_m + 2$ by representing $F_{m+1}$ in ...
0
votes
3answers
23 views

Solving for mod indirectly

How many positive integers $n$ exist such that $\frac{680}{n}$ is an integer? So, this is quite obvious, $680 \equiv 0 \pmod{n}$ How should I solve for $n$? There will be multiple $n$?
0
votes
0answers
28 views

>Find all pairs of positive integers $(m, n)$, so that $1 + x + x^2 +\ldots+x^m \mid 1 + x^n + x^{2n} +\ldots +x^{mn}$

Find all pairs of positive integers $(m, n)$, so that $1 + x + x^2 +\ldots+x^m \mid 1 + x^n + x^{2n} +\ldots +x^{mn}$ I have to find $(m, n)$ such that ...
2
votes
2answers
120 views

If GCD of a list of numbers is 1, is it a necessary condition that GCD of at least one pair of numbers from the list should be 1?

Suppose our numbers are {2, 6, 3}. GCD (2, 6, 3) = 1, GCD (2, 6) = 2, GCD (6, 3) = 3, but GCD(2, 3) = 1 If GCD(a,b,c) = p, GCD(a,b) = q, GCD(b,c) = r, GCD(c,a) = s, is it possible that p = 1 and (q ...
0
votes
1answer
22 views

Divisibility of binomial coefficients

I have got this series of binomial coefficients - $${2n\choose 0}+3\times{2n\choose 2}+3^{2}\times{2n\choose 4}+\ldots +3^{n}\times{2n\choose 2n}$$ I have to prove this to be divisble by ...
4
votes
3answers
159 views

What is so great about 7?

I'm going to write down my problem verbatim: Write down the integers from $1$ to $50$ in rows of $10$ numbers each. Mark out $1$, and then cross out all multiples of $2$ greater than $2$ ...
1
vote
2answers
28 views

GCD Using Euclidean Algorithm

How do I find the GCD of $65024$ and $128397$? And how do I express the GCD as a linear combination of $65024$ and $128397$ of the form $g = a\cdot 65024 + b\cdot 128397$? My work: $128397 = ...
1
vote
0answers
52 views

Evaluate $\sqrt{2^{2014} + 2^{2011} + 2^{2006}} \pmod{17}$

Evaluate: $$I = \sqrt{2^{2014} + 2^{2011} + 2^{2006}} \pmod{17}$$ $$I = \sqrt{2^{2006}\cdot (1 + 2^{5} + 2^{8} )} \pmod{17} = 2^{1003} \cdot \sqrt{2^8 + 2^5 + 1} \pmod{17}$$ The answer is $0$ ...
-1
votes
1answer
49 views

Solve $5991x + 289 \equiv 0 \pmod{2014}$

Solve: $$5991x + 289 \equiv 0 \pmod{2014}$$ $$5991x \equiv -289 \equiv 1725 \pmod{2014}$$ I need to find the inverse of $5991$ modulo $2014$. Start with Euclid's algorithm: $$5991 = 2(2014) + ...
2
votes
4answers
66 views

Proving that $x^5 = x \pmod{10}$ for every integer $x$. [duplicate]

Show that $x^5 = x \pmod{10}$ for every integer $x$. How can I approach this? Should I use induction? I am stuck trying to get it in terms of $x+1$. Some feedback would be appreciated.
2
votes
3answers
52 views

Proof of non divisibililty of $\binom{n}{r}$ with a prime $p$

I came across this : "It is possible to show that if $p$ is prime, $\binom{n}{r}$ is not divisible by $p$ if and only if the addition $r + (n-r)$, when written in base $p$, has no carries. This means ...
0
votes
1answer
21 views

Two recurrence relations gcd proof

Let $q_1, q_2,\ldots$ be a sequence of integers with $q_i\gt0$ for all $i\gt 1$. Define $(a_n)_{n\ge-1}$ and $(b_n)_{n\ge-1}$ by the following recurrence relations: $a_{-1}=0,\ a_0=1,\ b_{-1}=1,\ ...
1
vote
1answer
35 views

Is there a set of integers where all differences are relatively prime?

Is there an infinite subset $\mathcal S\subset \mathbb Z$ with the property that for any 4-tuple of distinct elements $x,y,z,w\in \mathcal S$ $$ \gcd(x-y,z-w)=1? $$
1
vote
3answers
49 views

If gcd$(a, 4) = 2$ and gcd$(b, 4) =2$, then gcd$(a + b, 4) = 4$ [on hold]

If gcd$(a, 4) = 2$ and gcd$(b, 4) =2$, then gcd$(a + b, 4) = 4$ can someone help me solve this.
2
votes
2answers
67 views

Determining $\gcd(94, 27)$

I want to determine $\gcd(94, 27)$. Using the Euclidean algorithm, I got \begin{align} 94 &= 27 (3) + 13 \\ \implies 27 &= 13 (2) + 1 \\ \implies \;\;2 &= 2 (1) \end{align} Does this ...
-1
votes
0answers
37 views

Is there an efficient method to search prime factors near $9^{9^9}$?

Since, the number $9^{9^9}$ is very special, is there a better method to search prime factors for a number near $9^{9^9}$ than simply trial division ? Especially, I searched prime factors of ...
0
votes
1answer
41 views

On no. of solutions of product of positive integers equal to sum

$n \ge 2$ be an integer , let $a(n)$ be the no. of solutions in positive integers of $x_1+x_2+...+x_n=x_1x_2...x_n ; x_1 \le x_2 \le ... \le x_n$ , then is it true that $a(n+1)=1 \implies n$ is ...
0
votes
3answers
18 views

Greatest common divisor of an integer 'a' and it's sum with 2.

I need to prove that the $\gcd(a, a+2)$ equals either 1 or 2. Intuitively this makes sense to me. If a is an odd integer then the gcd is 1, if a is even, the gcd is 2. I'm having trouble writing a ...
0
votes
2answers
44 views

If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$

Suppose that $k$, $n$, and $d$ are integers and $d$ is not $0$. Prove: If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$. You may not use the theorem stating the following: Let ...
2
votes
3answers
75 views

The number of positive integers less than 1000 with an odd number of divisors

How many positive integers less than 1000 have an odd number of positive integer divisors? Well I know that the number has to be composite because a prime number has 2 divisors, which are 1 and ...
3
votes
1answer
38 views

Way to show divisibility without using Euclid's lemma.

The generalized version of Euclid's lemma states that if $k|mn$ and that $\gcd(k, m) = 1$ then $k|n$. However, I noticed an alternative way of proving questions such as: if $2|n$ and $3|n$ show $6|n$ ...
3
votes
1answer
24 views

For $d \in \mathbb{Z}$, if $d\mid a$ and $d\mid b$, show that $d\mid(a+b)$ and $d\mid(a-b)$.

Let $d > 0$ and $d \in \mathbb{Z}$. If $d$ divides $a$ and $d$ divides $b$ then I want to show that $d$ divides $a+b$ and $a-b$. If $d$ divides $a$ then there exist an $m$ such that $a = dm$. If ...
2
votes
3answers
40 views

Proof of divisibility, given divisibility of a square

The below proof is incorrect. See the answers for more information. This question is in the context of exploring how to explain the process of developing a proof. When reading a proof on the ...
0
votes
0answers
21 views

Check if a set is a groebner basis, based on result of multivariate division algorithm

I've computed that the polynomial $f=x^2y+xy^2+y^2$ when factored with the two polynomials $f_1=y^2-1$ and $f_2=xy-1$, can be rewritten as $f=(xy-1)(x+y)+(y^2-1)(1)+(x+y+1)$ using the multivariate ...
11
votes
3answers
95 views

Prove that $2$, $3$, $1+ \sqrt{-5}$, and $1-\sqrt{-5}$ are irreducible in $\mathbb{Z}[\sqrt{-5}]$.

So the Norm for an element $\alpha = a + b\sqrt{-5}$ in $\mathbb{Z}[\sqrt{-5}]$ is defined as $N(\alpha) = a^2 + 5b^2$ and so i argue by contradiction assume there exists $\alpha$ such that $N(\alpha) ...
3
votes
5answers
71 views

Show that if $a$ is an integer, then 3 divides $a^3 - a $

Show that if $a$ is an integer, then 3 divides $a^3 - a $ we can write, where $k$ is an integer; $a^3 - a = 3k $ $a(a^2 - 1) = 3k $ Now if $a = k$ then $a^2 -1 = 3$ and $a= \pm2 $ so $ a^3 - a = ...
4
votes
2answers
45 views

Prove that $89|2^{44}-1$

Is there any easier (less no. of steps or calculations) proof for this using congruences: $89|2^{44}-1$. My proof: $$2^6\equiv-25\mod89$$ $$2^5\equiv32\mod89$$ Now square both equations: ...
0
votes
1answer
30 views

Divisiblity of $n$ with $a,b,c$ is relative prime to p

Given an arbitrary prime $p > 2011$. Prove that there exist positive integers $a,b,c$ such that there exists some numbers from $a, b, c$ that are relatively prime to $p$, and for all positive ...
0
votes
1answer
32 views

GCD : Number Theory Problem

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : If (x, 4) = 2 and (y, 4) =2, then (x + y, 4) = 4 where (a,b) denotes gcd of a & b ...
0
votes
4answers
37 views

GCD : Difference

I was working my way through some number theoretic proofs and being a newbie am stuck on this proof : Why does the gcd of two numbers , say (a,b) - also divides their difference : a-b My ...
12
votes
1answer
116 views

Are there infinitely many pairs of primes where one divides one more than the square of the other?

I have the following question on number theory that is eating my head. Are there infinitely many primes $p,q$ such that $p | (q^2 + 1)$ and $q | (p^2 + 1)$? I can see $13,5$ and $2,5$ has the ...
0
votes
1answer
52 views

Highest common factors of polynomials

Let h be a hcf of $f, g \in K[x]$ Then there exists polynomials a and b such that $h = af + bg$ Can anyone explain this theorem to me intuitively?
4
votes
3answers
134 views

True or False: $2^{2^{2011}} \text{ divides } 2^{2^{2012} }$

True or false: $$2^{2^{2011}} \text{ divides } 2^{2^{2012} }$$ Give your justifications. I don't know how to start this problem so far. But, I guessed like this, $$2^{\underbrace{2\times ...
2
votes
4answers
122 views

Prove that $p$ divides $F_{p-1}+F_{p+1}-1$ [duplicate]

Given the Fibonacci sequence $(F_n)$, defined by $F_0=0,F_1=1, F_{n+2}=F_{n+1}+F_n$, and $p$ an odd prime number, how to prove that $p$ divides $F_{p-1}+F_{p+1}-1$? Is induction a good idea here? ...
0
votes
3answers
40 views

Help me answer this Number Theory question on GCD (involves exponents) [duplicate]

Basically I need a good hint how to solve the problem.I have solved it partly. $gcd(2^a-1,2^b-1)=2^{gcd(a,b)}-1$. I have reached till: $gcd(2^a-1,2^b-1)=gcd(2^{a-b}-1,2^b-1)$ How to ...
1
vote
3answers
50 views

If $\gcd (a,b) = 1$, what can be said about $\gcd (a+b,a-b)$?

Suppose $a, b \in \mathbb{Z}$, $a > b$, and $\gcd (a,b) = 1$. What can be said about $\gcd (a+b,a-b)$? Is it true in general that $\gcd (a+b,a-b) \leq 2$?
1
vote
1answer
47 views

To find all positive integers $n$ such that $n|a^2-1 ; a \in \mathbb Z \implies n|a-1 $ , or $n|a+1$

How do we find all positive integers $n$ such that $n|a^2-1 ; a \in \mathbb Z \implies n|a-1 $ , or $n|a+1$ ? I have found that for any odd prime $p$ and $n \in \mathbb Z^+$ , $p^n|a^2-1 ; a \in ...
1
vote
0answers
38 views

Proving the Divisibility Rule for $3$ [duplicate]

Theorem: If 3 divides the sum of the digits of a number, then 3 divides that number
3
votes
1answer
54 views

Significance of GCD

I understand GCD mathematically but i can't figure out where to apply it. For eg I saw this problem today: Adam is standing at point $(a,b)\in\mathbb Z^2$ in an infinite 2D grid. He wants to ...
0
votes
0answers
11 views

What can we say about $\frac{s}{p}$, $\frac{p}{s}$ using these 3 imposed conditions?

What can we say (if anything) about $\frac{s}{p}$ or $\frac{p}{s}$ where $p$ and $s$ are integers greater than $1$ using the following three conditions: $p>s$, $s$ and $p$ are not both divisible ...
1
vote
2answers
17 views

12 column grid, how to calculate for columns(5,7,8,9,10,11)?

I am terrible at math, this is css/sass related, but it's mainly a math question. I feel like the answer is very easy. You can see for example col-1 is ...