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
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
59 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) + ...
0
votes
1answer
42 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
43 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? $$
4
votes
3answers
146 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
3answers
82 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.
0
votes
1answer
102 views

Two issues of Number Theory

Knowing in Fibonacci sequence$$u_n\mid u_m\Longleftrightarrow n\mid m$$ Question 1: In Fibonacci sequence, show that $$5\mid u_m\Longleftrightarrow 5\mid m$$ Show: $\Longrightarrow$ In ...
2
votes
2answers
74 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 ...
2
votes
3answers
405 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 ...
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 ...
2
votes
5answers
817 views

Suppose that $5\leq q\leq p$ are both prime. Prove that $24|(p^2-q^2)$. [duplicate]

Suppose that $5\leq q\leq p$ are both prime. Prove that $24|(p^2-q^2)$. This is what I got so far. I figured that since $p,q$ are bigger than $5$, there are only odd primes for this conjecture. ...
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 ...
11
votes
3answers
226 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) ...
11
votes
2answers
863 views

What is the remainder when $1! + 2! + 3! +\cdots+ 1000!$ is divided by $12$?

What is the remainder when $$1! + 2! + 3! +\cdots+ 1000!$$ is divided by $12$. I have tried to find the answer using the Binomial Theorem but that doesn't help. How will we do this? Please help.
2
votes
0answers
38 views

divisibility and k-power sum

Let $a_{1},\dots,a_{n},\,n>2$ distinct natural numbers. Prove that if $p_{1},\dots,p_{r}$ are prime numbers and they divide $a_{1}+\dots+a_{n}$ then exists an integer $k>1$ and a prime $p\neq ...
0
votes
1answer
66 views

Show that the number 9 divides the number $ m$ if and only if the sum of the digits of the number $ m $ is divisible by 9. [duplicate]

Show that the number 9 divides the number $ m$ if and only if the sum of the digits of the number $ m $ is divisible by 9. Show that the number 3 divides the number $ m$ if and only if the sum of the ...
2
votes
3answers
59 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 ...
3
votes
5answers
123 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 = ...
3
votes
6answers
123 views

Prove that $4^{2n+1}+3^{n+2} : \forall n\in\mathbb{N}$ is a multiple of $13$

How to prove that $\forall n\in\mathbb{N},\exists k\in\mathbb{Z}:4^{2n+1}+3^{n+2}=13\cdot k$ I've tried to do it by induction. For $n=0$ it's trivial. Now for the general case, I decided to throw ...
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 ...
5
votes
2answers
63 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: ...
1
vote
5answers
305 views

$24\mid n(n^{2}-1)(3n+2)$ for all $n$ natural problems in the statement.

"Prove that for every $ n $ natural, $24\mid n(n^2-1)(3n+2)$" Resolution: $$24\mid n(n^2-1)(3n+2)$$if$$3\cdot8\mid n(n^2-1)(3n+2)$$since$$n(n^2-1)(3n+2)=(n-1)n(n+1)(3n+2)\Rightarrow3\mid ...
12
votes
7answers
579 views

How can I find the possible values that $\gcd(a+b,a^2+b^2)$ can take, if $\gcd(a,b)=1$

If $\gcd(a,b)=1$, how can I find the values that $\gcd(a+b,a^2+b^2)$ can possibly take? I can´t find a way to use any of the elemental divisibility and gcd theorems to find them.
4
votes
0answers
135 views

Reducing multivariate rational fractions to lowest terms

I wish to simplify multivariate rational fractions to a canonical form. Thanks to some very helpful mathematically inclined people who verified that my understanding of Wikipedia was correct, I'm now ...
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? ...
4
votes
1answer
300 views

Comparing two definitions of a set of natural numbers

Let $n_1,n_2,N\in \mathbb{N}$. I want to show the following: The two sets \begin{align*} &\Delta(n_1,n_2,N)\\ =& \Big\{ a\cdot b: \quad a\mid {n_1}^2,~a^2 \mid {n_1}^2N ,\gcd\left(N ...
0
votes
1answer
57 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?
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
75 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 ...
3
votes
0answers
68 views

Trying to prove a congruence for Stirling numbers of the second kind

I am struggling with a demonstration for this: When $n$ and $m$ are 2 natural integers such that $n-m$ is odd, then the following congruence holds for Stirling number of the second kind ${n \brace ...
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
-2
votes
0answers
160 views

Prove that $n^4−1 $ is divisible by 5 when n is not divisible by 5. [duplicate]

Apparently the easiest method is to use proof by exhaustion, but I've no idea how. Any ideas/solutions? Prove that $n^4−1$ is divisible by 5 when n is not divisible by 5.
2
votes
1answer
125 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 ...
4
votes
1answer
482 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 ...
2
votes
3answers
751 views

Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$.

Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$. I thought I would do the following ... As $n$ is not divisible by $2$ and $3$ then ...
1
vote
2answers
89 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 ...
1
vote
2answers
121 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 ...
10
votes
4answers
3k views

Why are all non-prime numbers divisible by a prime number?

In Euclid's infinite prime numbers proof, the logic is as follows: Assume a set $S$ of all prime numbers in existence is finite (there are a finite amount of primes) Then there must be a greatest ...
-1
votes
1answer
101 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$ ...
7
votes
2answers
127 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 ...
1
vote
2answers
96 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. ...
0
votes
1answer
45 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
0answers
39 views

the division $14^{256}$ by $17$ [duplicate]

What the rest of the division $14^{256}$ by $17$? $$14^2\equiv9\pmod{17}\\14^4\equiv13\pmod{17}\\14^8\equiv16\equiv-1\pmod{17}\\(14^8)^{32}\equiv(-1)^{32}\equiv1\pmod{17}$$The rest is $1$, ...
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
1answer
19 views

Average Speed Calculation

An airplane leaves New York at 1:10 PM and arrives in Miami, 1125 miles away, at 3:40 PM. What is its average speed in miles per hour? Isn't the formula speed = distance/time? It didn't work for me ...
3
votes
4answers
116 views

$2^{2^n}+5^{2^n}+7^{2^n}$ is always divisible by $39$

This problem is really bothering me for some time, I appreciate if you have some idea and insight. Prove that $$2^{2^n}+5^{2^n}+7^{2^n}$$ is divisible by $39$ for all natural numbers ...