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)

0
votes
0answers
25 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
28 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
19 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
119 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
22 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
21 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
157 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
65 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.
1
vote
3answers
50 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
20 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
66 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
34 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
38 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
17 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
43 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
71 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
37 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
39 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
94 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
29 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
132 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
53 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 ...
2
votes
1answer
80 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
70 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
35 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
33 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
3answers
118 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
42 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 ...