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)

8
votes
3answers
106 views

g.c.d.{$m^p-m:m=2$ to $n$} $= ?$

Let $p$ be an odd prime and $n>2$ is an integer , then what is the $g.c.d.$ of the numbers {$m^p-m:m=2$ to $n$} ? (by Fermat's little theorem it is easy to see , $2p$ divides the g.c.d. , but I can ...
7
votes
11answers
368 views

3 never divides $n^2+1$

Problem: Is it true that 3 never divides $n^2+1$ for every positive integer n? Explain. Explanation: If n is odd, then $n^2+1$ is even. Hence 3 never divides $n^2+1$, when n is odd. If n is even, ...
10
votes
2answers
185 views

If $n\in\mathbb N$ and $4^n+2^n+1$ is prime, prove that there exists an $m\in\mathbb N\cup\{0\}$ such that $n=3^m$.

If $n\in\mathbb N$ and $4^n+2^n+1$ is prime, prove that there exists an $m\in\mathbb N\cup\{0\}$ such that $n=3^m$. I.e. if $4^n+2^n+1$ is prime, prove that $n=3^m$, where $m\in\mathbb N\cup\{0\}$. ...
2
votes
1answer
74 views

If $p$ is prime and $p>3$ and $k,l,m,n,p\in\mathbb N$ and $p^k+p^l+p^m=n^2$, prove that $8\mid p+1$.

If $k,l,m,n,p\in\mathbb N$ and a prime number $p>3$ that satisfies $$p^k+p^l+p^m=n^2$$ is chosen, prove that $8\mid p+1$. $n^2$, when divided by $8$, gives a remainder $1$ (it can't give the ...
1
vote
3answers
48 views

Irreducibility of gcd/lcm or lcm/gcd

Consider two irreducible fractions: $r_{1} = \frac{p_{1}}{q_{1}}$ $r_{2} = \frac{p_{2}}{q_{2}}$ Are these two fractions: $r_{3} = \frac{\text{gcd}\left(p_{1}, p_{2}\right)}{\text{lcm}\left(q_{1}, ...
6
votes
2answers
436 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 tried to do it using binomial theorem but that doesn't help. How will we do this? Please help.
0
votes
1answer
83 views

Proof that the euler totient function is multiplicative, correctness?

I've tried proving that $\varphi(mn) = \varphi(m)\varphi(n)$ (if $gcd(mn)=1$). The proof I try to setup doesn't look like the proof I find in textbooks, where am I going wrong? Proof: We try to ...
2
votes
4answers
146 views

Divisibility by seven

Given number n, whose decimal representation contains digits only $1, 6, 8, 9$. Rearrange the digits in its decimal representation so that the resulting number will be divisible by 7. If number is m ...
1
vote
2answers
87 views

Extended Euclidean Algorithm problem

I'm confused about how to do the extended algorithm. For example, here's the gcd part gcd(8000,7001) $$\begin{align}8000 &= 7001\cdot1 + 999\\ 7001&=999\cdot 7+8\\ 999&=8\cdot 124+7\\ ...
1
vote
1answer
84 views

If $m,n\in \mathbb N$ and $n>m$, prove that $lcm(m,n)+lcm(m+1,n+1)>\frac{2mn}{\sqrt{n-m}}$.

Where $lcm$ is the least common multiple. I've changed it to: $$\frac{mn}{\gcd(m,n)}+\frac{(m+1)(n+1)}{\gcd(m+1,n+1)}>\frac{2mn}{\sqrt{n-m}}$$ Can't see how to continue. Is there a way to ...
1
vote
2answers
68 views

Whether m divides n! or not?

I have a big number ($n!$). And I want to know whether $n!$ dividable by $m$ or not. Well calculating $n!$ is not a good idea so I'm looking for another way. Example: $9$ divides $6!$ $27$ does ...
2
votes
2answers
86 views

Number of Solutions

How to to calculate the number of solutions for the equation $A+B-\gcd(A,B)=R$ where we are given $R$ in the question ? In this question we have to calculate the number of combinations of $A$ and $B$ ...
1
vote
2answers
44 views

Is this a valid proof that $\{ax + by|x,y \in \Bbb Z\}= \{n\times \gcd(a, b) |n\in \Bbb Z\}$?

I'm trying to prove that $\{ax + by|x,y \in \Bbb Z\}= \{n\times \gcd(a, b) |n\in \Bbb Z\}$, but I'm unsure on the . The main proposition I'm using to solve this is that $\exists x,y, ax+by = \gcd(a, ...
1
vote
1answer
49 views

Prove thant if $a/b + c/d \in \mathbb Z, (a:b)= 1, (c:d) =1 $ then $|b|=|d|$

Be $a,b,c,d \in \mathbb Z, b \ne 0, d \ne 0.$ Prove that if $a/b + c/d \in \mathbb Z, (a:b)= 1, (c:d) =1 $ then $|b|=|d|$
4
votes
1answer
84 views

Simple method for $\frac{(2n+1)!}{(n!)^{2}}$ divide $lcm(1,2,\ldots,2n+1)$

The question is to prove that $\frac{(2n+1)!}{(n!)^{2}}$ divides $lcm(1,2,\ldots,2n+1)$. This seems like it should be a simple question, but try as I might, I can't seems to find any way that does ...
0
votes
3answers
78 views

If $a|(b-c)$ does it follow that $a|(b+c)$?

I plug in numbers and this seems to work but how can this be proved? If: $a|(b-c)\space \rightarrow\space ak=b-c$, but I can't see how this would mean $a|(b+c)$ If this is true, how can this be ...
0
votes
2answers
35 views

Prove $(\forall n \in \Bbb N)[\gcd\left(n,(16n+1)^3\right)=1]$

Prove $(\forall n \in \Bbb N)[\gcd(n,(16n+1)^3)=1]$ Knowing that $\gcd(a,b)=\gcd(a,b+a\times k)$ with $k \in \Bbb Z$ $$\gcd\left(n,(16n+1)^3\right)=\gcd\left((16n+1)^3,n\right)=d$$ ...
1
vote
2answers
48 views

Proof about GCD's

Prove that if $a, b$ and $c$ are integers with $b \neq 0$ and $a=bx+cy$ for some integers $x$ and $y$, then $\text{gcd}(b,c) \le \text{gcd}(a,b).$ I don't understand how to show (b,c) is less than ...
0
votes
1answer
47 views

Inductive proof for gcd

Proof that $(\forall n \in \Bbb N)[\gcd(n,(25n+1)^3)=1]$ By the inductive method: $p(n):\gcd(n,(25n+1)^3)=1$ $p(1): \gcd(1,26^3)=1 \implies p(n)\equiv \text{True}$ $p(n): $I assume that $p(n)\equiv ...
3
votes
3answers
68 views

Show that there are infinitely many values of n for which $23| n^2 + 14n + 47$

Show that there are infinitely many values of n for which $23| n^2 + 14n + 47$ So far I have shown that there is in fact some solution. By the definition of division, $n^2 + 14n +47 = 23k$ Thus, ...
1
vote
2answers
115 views

Let $d$ be a positive odd integer. Prove that there exists a positive $n \le d$ such that $d | 2^n − 1$.

I'm stuck on this question from my textbook which doesn't even have a solution. Any ideas ?. Help would be much appreciated. $$ d\, \left\vert\right.\, \left(2^{n} − 1\right) $$
2
votes
5answers
116 views

How to prove that $x^a-1|x^b-1 \Longleftrightarrow a|b$.

Prove that $x^a-1|x^b-1 \Longleftrightarrow a|b$, where $x \ge 2$ and $a,b,x \in \Bbb Z$. I've tried the following in attempting to solve this: $$a|b \rightarrow aq=b \rightarrow x^{aq}=x^b ...
0
votes
2answers
48 views

What are a and b?

$a$ and $b$ are two positive integers. If $ab=1260$, $gcd(a,b)=3$, and when $a$ is divided by $b$ the remainder is 18, what are $a$ and $b$? How do you solve this? EDIT It looks like an ...
2
votes
4answers
78 views

Prove: If $\gcd(a,b) = 1$ and $c|a$ and $d|b$, then $\gcd(c,d)=1$

I've a problem proving the following: If $\gcd(a,b) = 1$ and $c|a$ and $d|b$, then $\gcd(c,d)=1$ I've tried to set $a = c\cdot p$ and $b = d\cdot q$. But then I'm stuck proofing it formally.
1
vote
1answer
63 views

Prime power factorization of $10^n+1$

I have bee trying to prove/disprove the statement, $$\text{Let}\; 10^n+1 = p_{k}^{\;\alpha_k}p_{k-1}^{\;\alpha_{k-1}}\dots p_0, \text{where each}\; p_i \;\text{is a distinct prime.} \text{Then}\; ...
2
votes
2answers
106 views

If $a,b,c \in \mathbb N$ and $\gcd(a^2-1,b^2-1,c^2-1)=1$, prove that $\gcd(ab+c,bc+a,ca+b)=\gcd(a,b,c)$.

The whole problem is in the title. I'm out of ideas and can't think of a way to solve this, so I'd like to get some help. Thanks.
4
votes
2answers
123 views

$2^5 \cdot a^b=2,5ab$

I came across this problem in an elementary number theory book, and I think I solved it. Well, the question is posed as $2^5 \cdot 9^2 = 2,592$. Are there any other pairs $a,b \in \mathbb{Z}$ such ...
8
votes
1answer
414 views

$f'/f\in\mathbb{Z}[[x]]$ for polynomials vs. formal power series $f$

I am curious about the following problem from MIT's Problem Solving Seminar (#26 here, though the link may stop working after a few weeks): Let $f(x) = a_0+a_1x+\cdots\in\mathbb{Z}[[x]]$ be a ...
1
vote
1answer
84 views

If $a,b \in\mathbb N$ and $\gcd(a,b)=1$, prove that $\gcd(a+b;a^2+b^2)= 1$ or $2$.

If $a,b \in\mathbb N$ and $\gcd(a,b)=1$, prove that $\gcd(a+b,a^2+b^2)$ is always equal to either 1 or 2, where $\gcd$ is the greatest common divisor. I haven't really ever solved a problem like this ...
1
vote
0answers
56 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
2
votes
2answers
71 views

Proof that $\gcd$ divides $\operatorname{lcm}$

Show that the following conditions are equivalent: i) There exist positive integers $a, b$ such that $\gcd(a,b)=d$ and $\operatorname{lcm}(a,b)=m$. ii) $d\mid m$
2
votes
2answers
61 views

What is the highest power of a prime that divides nPr?

I know that the highest power of a prime which divides $n!$ is given by $$\left[\frac np\right]+\left[\frac n{p^2}\right]+\left[\frac n{p^3}\right]...$$ Where $[x]$ is the greatest integer function. ...
1
vote
6answers
261 views

Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.

Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers. I think I have to use the contrapositive to solve this. So I assume $\neg ...
0
votes
1answer
317 views

Every natural number greater than 1 is divisible by a prime number

Sorry if this question has been asked, but a couldn't find one using the method I need. I want to prove that every natural number greater than 1 is divisible by some prime number using the WOP. I ...
0
votes
2answers
41 views

Question about Divisibility

Suppose we are given the following: $p$ is a prime number; $a, c \in \mathbb{Z}$ and $ n \in \mathbb{N}$. Can I prove that there exists $m \in \mathbb{N} $ and $b \in \mathbb {Z} $ such that ...
-1
votes
2answers
53 views

For any integer $n\ge0$ it follows that $9\mathrel|(4^{3n}+8)$?

I have been trying to use induction in order to prove the above statement but I always reach a dead end. How can this statement proven via induction? Thank you!
0
votes
1answer
81 views

Proof polynomial is always divisible by number

Given $f(x) \in \mathbb{Z} [x] $ a polinomyal, that evaluated in any $a \in \mathbb{N} $, results allways in a multiple of 101 or a multiple of 107 (both prime numbers). Prove then, that $f(x)$ it's ...
0
votes
2answers
125 views

Polynomial divisibility

Given $p(x) \in \mathbb Q[x] $ an irreducible polynomial, and $\alpha \in\mathbb C $ root of $p(x)$. Prove that if $q(x) \in \mathbb Q[x]$ it's a polynomial, such $q(\alpha) = 0$ then $p(x) \mid ...
1
vote
5answers
73 views

Show that if $(a,b)=1$, $a\mid c$ and $b\mid c$, then $a\cdot b\mid c$

Show that if $(a,b)=1$, $a\mid c$ and $b\mid c$, then $a\cdot b\mid c$. Tried $c=a\cdot k$ and $c=b\cdot j$ with $k,j\in\mathbb{N}$ then $a\cdot b\mid c^2=c\cdot c$.
3
votes
2answers
64 views

Why is the coefficient in front of $\sqrt n$ always 1 in the intermediate terms for finding the continued fraction expansion of $\sqrt n$?

After playing around on paper for a bit, I came up with a short python generator to find the continued fraction expansion of $\sqrt n$. I understand why it gets the right answer when it gets an ...
2
votes
2answers
399 views

how many pairs $(A, B)$ are there such that: gcd $(A, B) = A \oplus B$

Given an integer N,how can I find how many pairs $(A, B)$ are there such that: gcd $(A, B) = $A$ \oplus B$ where $ 1 ≤ B ≤ A ≤ N $. Here gcd $(A, B)$ means the greatest common divisor of the ...
0
votes
1answer
43 views

gcd & lcm in a PID

In a PID, $l={\rm lcm}(a,b)$ and $d=\gcd(a,b)$. Is it always true that the following product ideals are equal? $$<d><l> = <a><b>$$ Thanks in advance -- Mike
0
votes
0answers
105 views

Dynamic programming algorithm for GCD?

I can't seem to find a clear answer on this. I'm inclined to believe that there is not a DP solution for GCD, given the lack of information so far in my searches on the subject. I suppose that in ...
0
votes
0answers
52 views

Distribution and upper bound of mimic numbers

Let the notation $ a\mid b $ denote ''$ a $ divides $ b $''. The mimic function in number theory is defined as follows [1]. Definition For any positive integer $ \mathcal{N} = ...
2
votes
3answers
114 views

How to prove or disprove that $\gcd(ab, c) = \gcd(a, b) \times \gcd(b, c)$?

I'm new to proofs, and am trying to solve this problem from William J. Gilbert's "An Introduction To Mathematical Thinking: Algebra and Number Systems". Specifically, this is from Problem Set 2 ...
4
votes
3answers
120 views

How many numbers $k$ of $200 \choose k$ are divisible by $3$? $k \in \{0,1,2,\cdots 200\}$

"How many of the numbers (200 Choose k), where k is an element of the set {0,1,2,3,4,....,200} are divisible by 3? " Here is my thinking: (200 Choose 0,1, and 2) are not multiples of 3 but every ...
4
votes
5answers
145 views

If $\gcd(a,b)=1$ then, $\gcd(a^2,b^2)=1$ [duplicate]

Prove or disprove 'If $\gcd(a,b)=1$ then, $\gcd(a^2,b^2)=1$, with $a,b\not= 0$' I need to prove this statement. I think it is true and also the converse is true. I took some examples such as ...
-1
votes
1answer
48 views

Proof by induction and divisibility $21 | (4^{n+1} + 5^{2n-1}) $ [duplicate]

Prove by induction: $21 | (4^{n+1} + 5^{2n-1}) $ Skipping through the basis and onto the induction: $4\cdot 4^{n+1}+5^2 \cdot 5^{2n-1}=21a $ for some integer $a$ The following steps were: ...
1
vote
5answers
146 views

$2730\mid n^{13}-n\;\;\forall n\in\mathbb{N}$

Show that $2730\mid n^{13}-n,\;\;\forall n\in\mathbb{N}$ I tried, $2730=13\cdot5\cdot7\cdot2$ We have $13\mid n^{13}-n$, by Fermat's Little Theorem. We have $2\mid n^{13}-n$, by if $n$ even ...
0
votes
2answers
33 views

If u|s and v|t and gcd(s,t) = 1 then gcd(u,v) = 1

Proposition 1. If $\def\divides\mathrel{|}u \divides s$ and $v \divides t$ and $\gcd(s,t) = 1$ then $\gcd(u,v) = 1$. Solution. Assume $u \divides s$ and $v \divides t$. Since $\gcd(u, v) \divides u$, ...