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

learn more… | top users | synonyms

0
votes
4answers
96 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
34 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 ...
5
votes
4answers
190 views

Finding the possible Least Common Multiples of of numbers with Highest Common Factor 8

The Highest Common Factor of two numbers is 8. Which one of the following can never be their Least Common Multiple? The choices are as follow: A. 8 B. 12 C. 60 D. 72 The answer key states ...
1
vote
2answers
46 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 ...
2
votes
3answers
202 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
26 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
36 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
162 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
34 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
181 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
42 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
53 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
55 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
72 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
67 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
36 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
42 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? $$
2
votes
3answers
75 views

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

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
73 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 ...
0
votes
3answers
23 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
61 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
334 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
55 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
26 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
55 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 ...
11
votes
3answers
214 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
116 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 = ...
5
votes
2answers
61 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
31 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
2answers
58 views

If $\gcd (x,4) = 2$ and $\gcd(y,4) = 2$ then $\gcd(x+y,4) = 4$

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 the ...
0
votes
4answers
82 views

GCD : Why does the GCD of two numbers divides their 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 ...
11
votes
1answer
170 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
56 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
145 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
132 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
60 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
70 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
49 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
43 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
1
vote
2answers
60 views

For every natural number $n$, $ 3^{3n} - 1$ is divisible by $26$.

Use induction to prove that for every natural number $n$, $ 3^{3n} - 1$ is divisible by $26$. I can see that for $n=1$, $ 3^{3} -1=26\cdot 1$. As for inductive step, assuming that the statement ...
4
votes
1answer
445 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 ...
1
vote
2answers
103 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 ...
2
votes
1answer
121 views

Algebraic number theory exercise

I'm trying to do the following exercise from Neukirch's Algebraic Number Theory (exercise 2, $\S 1$, chapter 1): Show that, in the ring $\mathbb{Z}[i]$, the relation ...
-1
votes
1answer
91 views

probability divisible by 11 [closed]

$S$ is a set of the natural numbers with $10$ digit which each of the digits is different such $2901843756$. If a number is choosen fron set $S$ then the probability the number is divisible by $11$ ...
1
vote
2answers
92 views

Converting Decimal to Hexadecimal

MathExchange, I am trying to learn more about computers, and one thing I have opted to teach myself is decimal to binary, and decimal to hex conversion. From the web, I have found tutorials on ...
0
votes
0answers
35 views

Does this notation mean what I intend?

I was looking at divisibility rules earlier today and noticed that several of them had the same form, i.e. truncating the last digit and then adding or subtracting a multiple of it to the truncation. ...
7
votes
2answers
126 views

suppose that $n$ is natural number and even, show that $n \nmid 1^n +2^n+3^n + \ldots (n-1)^n$.

suppose that $n$ is natural number and even, show that $n \nmid 1^n +2^n+3^n + \ldots (n-1)^n$. so I put $n=2k$ and I supposed $n \mid 1^n +2^n+3^n + \ldots (n-1)^n$ then with a little calculation we ...
0
votes
1answer
43 views

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

How do we find all positive integers $n$ such that $a\in \mathbb Z ; n|a(a-1) \implies n|a $ , or $n|a-1$ ? The primes certainly satisfy this condition ; what other integers do satisfy this condition ...
0
votes
1answer
42 views

For odd $n$, there is an $m$ such that $n \mid 2^m-1$

I am really stuck with this question: Suppose $n$ is an odd positive integer. Prove that there exists a positive integer $m$ such that (2^m − 1)\n . (Here, “divides” means that when 2^m − 1 is ...
1
vote
2answers
88 views

Divisibility of $987x^n − F_nx^{16} + F_{n−16}$

If $F_n$ is $n^{th}$ Fibonacci number, and polynomials $P_n(x)$ are defined as $987x^n − F_nx^{16} + F_{n−16}$, prove that for all $n ≥ 1$, $P_n(x)$ is divisible by $x^2−x−1$. This is from a ...