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)

3
votes
1answer
57 views

Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$

Question: Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$ I know that it is possible to solve by factoring $n^3+1$ and showing that $n+1$ is a multiple, but I would like to show this via ...
1
vote
1answer
91 views

$n$ is a divider of $c$ if and only if $n = 2(c \mod (n-1)) - (c \mod(n-2)) + 2$

While working on Integer factorization problem I came to this conclusion: If and only if $n$ is a divider of $c$ $$c\mod n = 0$$ Than $$n = 2(c \mod (n-1)) - (c \mod(n-2)) + 2$$ c,n are positive ...
3
votes
9answers
161 views

Prove that for any integer, $n^2 + 5$ is not divisible by $4$.

So I got that there is two cases: odd or even. If odd then say $n^2$ is $(2k+1)^2 = 4k^2 + 4k + 1.$ then $4k^2 + 4k + 1 + 5$ would need to be divisible by 4 and I don't know where to go from there. ...
3
votes
3answers
63 views

Proving $ab(a+b)+ac(a+c)+bc(b+c)$ is even

Prove that $\forall a,b,c\in \mathbb N: ab(a+b)+ac(a+c)+bc(b+c)$ is even I tried to simplify the expression to something that would always yield an even number: $ (a+b+c)(ab+ac+bc)-3abc$ but ...
0
votes
1answer
28 views

Proving a number doesn't divide another and proving $lcm$ using the definition

Say I have two integers $a,b$ and I want to prove that $a\not \mid b$ or $ak\neq b$, do I have to take two adjacent $k$s such that $ak_1 < b$ and $ak_2> b$? Is there another way? Another ...
2
votes
4answers
53 views

Proving that if $8\mid (n^2+2n)$ then $2\mid n$

Let $n\in \mathbb N$ prove that if $8\mid (n^2+2n)$ then $2\mid n$. From the given, there exists $k\in \mathbb N$ such that $8k= (n^2+2n)$, take $k=1$, and we get $2\cdot 4 = n(n+2)$. Now my ...
9
votes
3answers
720 views

How many 0's are in the end of this expansion?

How many $0's$ are in the end of: $$1^1 \cdot 2^2 \cdot 3^3 \cdot 4^4.... 99^{99}$$ The answer is supposed to be $1100$ but I have absolutely NO clue how to get there. Any advice?
4
votes
1answer
113 views

Show that $\mathrm{gcd}(x+4,x-4)$ divides $8$ for all integers $x$.

I want to prove that $\mathrm{gcd}(x-4,x+4)$ divides $8$ for all $x\in \mathbb{Z}$ Since they are both polynomials of degree $1$, it suggests that the $\mathrm{gcd}$ is a constant. Using Euclidean ...
1
vote
1answer
29 views

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.. I am totally lost; at first I thought this could be done by induction, but unfortunately this is not possible (at least I ...
0
votes
1answer
50 views

If $a^2$ divides $b^3$, then $a$ divides $b$.

I want to prove or provide a counterexample to the following statement: $a^2|b^3 \Rightarrow a|b$. I know that $a^k|b^k \Rightarrow a|b$. My thought is that, e.g in the case of $k = 3$, where we ...
1
vote
2answers
51 views

If $X$ and $Y$ are coprime to $Z$, then so is their product $XY$

Given is $X$ is coprime to $Z$ and $Y$ is coprime to $Z$ prove $XY$ is coprime to $Z$. I know you can use Bezout's lemma to say $1=aX+bZ$ and $1=cY+dZ$ but I don't know how to actually do the proof. ...
4
votes
1answer
66 views

Prove that there are no positive integers $a, b$ and $n >1$ such that $a^n – b^n$ divides $ a^n + b^n$.

Prove that there are no positive integers $a$ , $b$ and $n>1$ such that $a^{n}–b^{n}$ divides $a^{n}+b^{n}$. Can someone provide me a proof of this and explain it to me please.
0
votes
2answers
32 views

If I have a polynomial $x^2(1-m^2) - x2m^2 - (m^2 + 1)$ with a solution at $x = -1$, how do I get the other root

If I have a polynomial $x^2(1-m^2) - x2m^2 - (m^2 + 1)$ with a solution at $x = -1$, then I know I can just take $x^2(1-m^2) - x2m^2 - (m^2 + 1)$ and divide it by $x+1$ to get the other root. In a ...
1
vote
1answer
40 views

If $p$ is a prime and $p$ divides $a^3$ then $p$ divides $a$ [closed]

I have to either give a proof or provide a counterexample for this question. $a, b$ are non-zero intergers. If $p$ is a prime and $p|a^3$ then $p|a$ I think this is true but do not know how to go ...
0
votes
1answer
41 views

Prove elements of a set are not uniquely representable.

Let $E = \{2k: k \in \Bbb{N}\}$, and let $M = \{m = (2r)(4a + 2) : r, a \in \Bbb{N}\}$. Prove that some elements in $E$ are not uniquely representable as products of elements of $M$, e.g. ...
0
votes
1answer
85 views

Solve $9x^8\equiv 8\pmod{17}$

$$9x^8\equiv 8\pmod{17}$$ Is there a way to solve this with out testing all integers $x$ between $1$ and $17$ ?
1
vote
2answers
77 views

The equation $x^4+y^4=z^2$ has no integer solution

The equation $$x^4+y^4=z^2$$ has no integer solution for $(x, y, z), x \cdot y \neq 0 , z >0$. We suppose that there is a solution $(x, y, z)$. We consider the set $$M=\{z \in \mathbb{N} | ...
0
votes
1answer
40 views

If $p^q - 1$ is a prime, then $p=2$ and $q$ is a prime [duplicate]

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : If $p$ and $q$ are positive integers ($\mathbb{Z}^+$) such that $q \gt 1$ and $(p^q - 1)$ is ...
0
votes
1answer
22 views

How to use totient function here?

I have asked this before, but I had no idea how to use Totient, now I do here is the questions: How many positive integers $< 2013$ cannot be divided by $2, 3, 5$ ?? An advice given was find ...
2
votes
1answer
50 views

For what positive integer values $b,d$ does $(b^2-d)\mid(b^2-1)?$ hold?

I am curious about the answer to the following questions: And hope that you can help me For what positive integer values $b, d$ does $$(b^2-d)|(b^2-1)?$$ hold? Is it correct that the only ...
2
votes
5answers
129 views

The divisibility of $a^p-1$ by $a-1$ and by $(a-1)^2$

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : Let a $\geq$ 2 and p be any positive integers , then prove that : $(a-1) \mid(a^p - ...
2
votes
1answer
25 views

Find $a$ and $b$ such that $g$ divides $f$ evenly

$f=2X^4-3X^2+aX+b,\ g=X^2-2X+3, \ f,g \in \mathbb{Q}[X]$ I have tried to divide $f$ by $g$ but I get $ (a+10)X +b +3$ as the remainder which looks like a bad result. I have, also, tried to factor ...
0
votes
1answer
39 views

How does the Euler Totient Function apply here?

How many positive integers $< 2013$ are divisible by $2$ Can I somehow use Euler's Totient function to find this?
4
votes
2answers
56 views

Suppose $\sqrt2=a/b$, with $gcd(a,b)=1$. Then $3|(a^2+b^2)$ implies that $3|a$ and $3|b$,

Suppose $\sqrt2=a/b$, with $\gcd(a,b)=1$. Then $a^2=2b^2$, so that $a^2+b^2=3b^2$. But $3|(a^2+b^2)$ implies that $3|a$ and $3|b$, a contradiction. I don't understand how $3|(a^2+b^2)$ implies that ...
0
votes
1answer
49 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
65 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
3answers
27 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 ...
1
vote
2answers
48 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
94 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
32 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
37 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
163 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
34 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
143 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
31 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
178 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
35 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
52 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
71 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
66 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
28 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
40 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
55 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
70 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
21 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
59 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
180 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
50 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$ ...