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
2answers
35 views

How would I prove for all a that a divides zero

I'm trying to prove for all a such that a divides zero. I can explain verbally why it works but I can't seem to be able to write it down in "proof" form. Could someone help me out?
1
vote
2answers
34 views

Proof: Each common divisor c of a,b divides GCD(a,b)

there already exists a proof for this theorem: http://www.proofwiki.org/wiki/Common_Divisor_Divides_GCD This one, however, uses Bêzout's Identity. I'm not allowed to use this for the proof. So, I ...
0
votes
2answers
47 views

Bezout's Identity for polynomials

Im working out a problem where I find out the GCD of two polynomials using Euclid's Algorithm, and then I need to use Bezout's Identity to make $\gcd(r,s)=ra+sb$ The question gives me $x^5+1$ and ...
1
vote
2answers
33 views

Finding a gcd in the form of a monic polynomial

The question is to find the greatest common divisor (in the form of monic polynomial) in $\Bbb F_5[X]$ of $f=x^2-x+4$ and $g=x^3+2x^2+3x+2$ I used the Euclidian Algorithm for polynomials and found ...
1
vote
0answers
37 views

Congruence equations

Given positive integer $Z, N$ and a set of positive integer $S$. Find smallest $k \in \mathbb{Z^+}$ such that $$a*k +1 \equiv Z \pmod N \ a\text{ is a positive integer that we don't know, and}\\ i*k ...
1
vote
3answers
23 views

Greatest Common Divisor written proof

Here is what I am trying to prove: Let $a,b,c,d \in ℤ_+$ with gcd$(a,b)=1$. If $a|c$ and $b|c$, prove that $ab|c$. Does the result hold if gcd $(a,b)\neq 1$ ? I know that gcd $(a,b)=1$ can be ...
4
votes
4answers
33 views

greatest common divisor of two primes a,b

Here is the question I am trying to prove: If $a,b$ are relatively prime and a>b prove that $\gcd(a-b, a+b) \in \{1, 2\}$. Can I begin with something like $(a-b)k + (a+b)l = d$ where $k,l$ are ...
14
votes
6answers
854 views

Divisibility criteria of 24. Why is this?

I am currently familiar with the method of checking if a number is divisible by $2, 3, 4, 5, 6, 8, 9, 10, 11$. While Checking for divisibility for $24$ (online). I found out that the number has to ...
1
vote
0answers
52 views

$\left\lfloor(\sqrt[3]{28}-3)^{-n}\right\rfloor$ is not divisible by 6 [duplicate]

let $n$ be a positive integer. Prove that the following expression: $$\left\lfloor(\sqrt[3]{28}-3)^{-n}\right\rfloor$$ is not divisible by 6. $\lfloor x\rfloor$ is the greatest integer less than or ...
0
votes
2answers
105 views

Proof about pythagorean triples $(a,b,c)$: At least one of $a$ and $b$ is even.

How should I go about proving at least one of a and b is even when $$a^2+b^2 = c^2$$ This is similar to A conjecture about Pythagorean triples, but I do not understand the steps written in there. ...
1
vote
2answers
40 views

How do I prove divisibility by 3 without induction?

How do I prove that: $3$ divides $4^n-1$, where $n$ is a natural number, and $3$ divides $n^3-n$, where $n$ is a natural number? All without induction?(only number theory) Thanks !
0
votes
2answers
75 views

gcd multiplied by lcm

I've encountered a very confusing problem in my homework. Let a and b natural numbers. Then, let x = gcd(a,b) * lcm(a,b). The question asks what [number] is x below, in terms of a and b. I do not ...
0
votes
4answers
74 views

Show {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$}

I have the following problem: Let $a, b \in\mathbb{Z}$. Show that {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$} I understand that the Bezout's lemma says that $gcd(a,b) = ...
1
vote
1answer
38 views

show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$.

show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$. My Work: I considered the case where $n =-1$ , and the case $n \not= 1$. So when $n\not= -1$ we can let $n^2 - ...
2
votes
1answer
47 views

Proving divisibility by using induction: $133 \mid (11^{n+2} + 12^{2n+1})$ [duplicate]

If $n > 0$, then prove the following by using induction: $$133|(11^{n+2} + 12^{2n+1}).$$
0
votes
1answer
45 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 ...
7
votes
6answers
2k views

Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. ...
1
vote
1answer
30 views

Find the next divisor without remainder

I divide a value and if the remainder is not 0 I want the closest possible divisor without remainder. Example: I have: $100 \% 48 = 4$ Now I am looking for the next value which divide 100 wihtout ...
0
votes
0answers
70 views

How do you justify the PigeonHole principle?

I am working on the problem below and just have two questions pertaining to my answers. 1) Am I clearly and correctly justfying my answers, anything I can improve on or explain better? 2) Are my ...
2
votes
1answer
42 views

Finding divisibility of a

Let $$a=\frac{72!}{(36!)^2}-1$$ Find whether $a$ is odd. $a$ is even. $a$ is divisible by 71. $a$ is divisible by 73. Multiple answers can be correct. I was able to find whether $a$ is even or ...
17
votes
5answers
1k views

How does one show that two general numbers $n! + 1$ and $(n+1)! + 1$ are relatively prime?

How does one show that two general numbers $n! + 1$ and $(n+1)! + 1$ are relatively prime? I don't mind if someone uses a different example, I want to learn how to prove this class of problems. My ...
8
votes
6answers
243 views

Understanding the proof of a formula for $p^e\Vert n!$

This is a proof from a book on number theory I'm reading. I'm having a hard time following. I think there's a variable here that means two different things at two different times... Theorem: If n is ...
0
votes
2answers
16 views

Relation of common divisors leading to integer results

When dividing an integer $a$ by 3 and 7 both results in an integer answer, I intuitively feel that $a/A$ with $A=21$ would also be integer, which seems related to the fact that $3\times7=21$. ...
1
vote
3answers
25 views

Looking for the lowest number divisible by 1 to A.

What would the math equation be for finding the lowest number divisible by 1 to A? I know factorial can make numbers divisible by 1 to A but that dosn't give me the lowest number. Example of what I'm ...
3
votes
2answers
27 views

If B is half of A and C is half of B and the sum of all them is 1 then, what is A?

If $B = A/2$, $C = B/2$, and $A + B + C = 1$, then what does $A$ equal? I'm baffled trying to solve this question I made up for "my own purposes" and this problem is always a bit off when I try to ...
2
votes
1answer
20 views

$\forall (p,k)\in\mathbb N^2$ with $k$ not divisible by $3$ : $1+p+p^2\mid 1+p^{2k}+(1+p)^{2k}$

I want to prove $\forall (p,k) \in\mathbb{N}$$^{2}$ with k not divisible by $3$ : $1+p+p^2\mid 1+p^{2k}+(1+p)^{2k}$ An attempt. $1+p+p²=(p-j)(p-\bar{j})$ with $j=e^{i\frac{2\pi}{3}}$. Then I prove ...
0
votes
1answer
51 views

Understanding a proof that $\gcd(a, b) = 1$ if $sa + tb = 21$ and $ua + vb = 10$

I am studying the solution to a problem: Suppose $a, b, s, t, u, v$ are integers such that $sa + tb = 21$ and $ua + vb = 10$. Show that $\gcd(a; b) = 1$. ...
-2
votes
1answer
52 views

Application of Euler's theorem

Let $x = 5$. Verify that $x$ divides $14^4 - 1$, but that $x$ does not divide $15^4 - 1$. Does the latter contradict Euler's Theorem?
0
votes
1answer
32 views

Continuity of identity in $p$-adic $\mathbb Z$

Say we have the $p$-adic metric in $\mathbb Z$ defined as $$ d_p(a,b)= \left\{\begin{align} &0 & a=b \\ &p^{-r} : p^r\mid (a-b), p^{r+1}\nmid (a-b) & a\neq b \end{align}\right. $$ I'd ...
0
votes
2answers
17 views

Divisibility question: if $a=be+r$, then $e$ $= ⌊bc⌋$

If $a$|$b$, with $a,b \in \Bbb Z$, then I know that $ a=be+r$, where $e\in \Bbb Z$ and $r$ is the residue. How can I prove that $e$ is equal to $⌊\frac ab⌋$? I'm missing this step in another proof ...
-1
votes
4answers
105 views

Showing the product of $5$ consecutive integers is divisible by $120$ [closed]

Use the sentence: $$a\mid c, \quad b \mid c, \quad (a,b)=1 \qquad \implies \qquad ab \mid c$$ and prove that the product of $5$ consecutive integers is divisible by $120$. How can I do this?
0
votes
2answers
53 views

Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation?

Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation? I know that it's reflexive, since $\gcd(a,a) > 1$. It's also symmetric since $\gcd(a,b) > 1$ iff $\gcd(b,a) > 1$. ...
1
vote
5answers
36 views

Find a polynomial $h(x)$ of maximum degree such that $h(x)$ is a factor of $f(x)$ and $g(x)$

Let $f(x)= x^3-x$ and $g(x)= x^4 + 3x^3 +x^2$ How can I find a polynomial $h(x)$ of maximum degree such that $h(x)$ is a factor of $f(x)$ and $g(x)$. My thoughts: there exist others polynomials ...
1
vote
1answer
22 views

Finding the remainder of a linear congruence

Okay so say I have $314^{420} \equiv r \pmod{1001}$ and I have to find what the remainder is, $r$ in this case. I know you could compute it by $gcd(314^{420}, 1001)$ and using EEA. But the numbers are ...
1
vote
4answers
67 views

Prove that $(ma, mb) = |m|(a, b)$

I'm trying to prove that $(ma, mb) = $|$m$|$(a, b)$ , where $(ma, mb)$ is the greatest common divisor between $ma$ and $mb$. My thoughts: If $(ma, mb) = d$ , then $d$|$ma$ and $d$|$mb$ → $d$|$max ...
1
vote
1answer
24 views

Are there infinite positive $n \in \Bbb N$ such that ($D^+_n$, |) is isomorphic to ($D^+_{4100}$, |)?

Are there infinite positive $n \in \Bbb N$ such that ($D^+_n$, |) is isomorphic to ($D^+_{4100}$, |)? I'm guessing no because I can't relate every element of ($D^+_{4100}$, |) to ($D^+_n$, |) because ...
0
votes
2answers
42 views

If $a$|$c$ and $b$|$c$, then $\frac {ab}{(a,b)}$|$c$

How can I prove that for $a,b,c \in ℕ^*$, if $a$|$c$ and $b$|$c$, then $\frac {ab}{(a,b)}$|$c$? This is what I've tried: $a$|$c$ and $b$|$c$ implies that $ba$|$bc$ and $ab$|$ac$, so $ab$|$bcx + ...
1
vote
3answers
65 views

Proving if $\gcd(c,m)=1$ then $\{x\in \Bbb Z \mid ax\equiv b \pmod m\} =\{x\in \Bbb Z \mid cax\equiv cb \pmod m\}$

Okay so I'm confused on how to approach this question. If $\gcd(c,m)=1$, then $S=T$ where $S=\{x\in \Bbb Z \mid ax\equiv b \pmod m\}$ and $T=\{x\in \Bbb Z \mid cax\equiv cb \pmod m\}$. I know ...
1
vote
2answers
26 views

Prove that $gcd(a, b) = gcd(a, b + ma)$?

How can I prove that gcd$(a, b)$ $=$ gcd $(a, b + ma)$? I have tried this: let $g = $gcd$(a, b) $, then $g$|$a$ and $g$|$b$. This means that $g$|$ax+by$. I don't know what to do next. Thanks.
6
votes
2answers
359 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.
2
votes
2answers
55 views

Suppose that $2^b-1|2^a+1$. Show that $b = 1$ or $2$.

I'm stuck with this one. I would appreaciate any idea how to prove this.
-1
votes
2answers
31 views

GCD or LCM confusion

Rosa is making a game board that is 16 inches by 24 inches. She wants to use square tiles. What is the largest tile she can use and how many square tile will be on her board? Need explanation on ...
6
votes
1answer
76 views

Bezouts Identity for prime powers

I have two prime powers $2^n$ and $5^n$ for some arbitrary $n$. Their gcd is $1$ but how do I get their integer linear combination which is $1$ in terms of $n$. In other words what will be the ...
0
votes
1answer
21 views

Number of positive $n$ s.t. $5|n^4 + 5n^2 + 9$

Find the total number of positive integers $n$ not more than $2013$ such that $n^4 + 5n^2 + 9$ is divisible by $5$. This problem was taken from Singapore Math Olympiad 2013, Open Section, First round. ...
4
votes
3answers
85 views

Why doesn't this calculation work?

I want to find some closed form for $\gcd(x^3+1,3x^2 + 3x + 1)$ but get $7$ which is not always true.
0
votes
3answers
25 views

Using long division on polynomials

Can anyone show me how to find $x^5 + 1$ divided by $x^3 + 1$? I tried using long division but I have that $x^3$ "goes into" $x^5 + 1$ about $x^2$ times but then I don't know how you're supposed to ...
1
vote
2answers
34 views

If $\exists$ $x,y \in \mathbb Z$ such that $ax+by=c$, then does $(a,b)|c$ or even stronger does $(a,b)=c$?

I think the first statement is true and the second statement is false. If so, I want to try to prove the first statement and find a counterexample (or proof) for the second. If $\exists$ $x,y \in ...
2
votes
2answers
69 views

Prove that if $\gcd(ab,c)=1$, then $\gcd(a,c)=1$.

I was told to prove $\gcd(ab,c)=1$ then $\gcd(a,c)=1$. I picked a number $p$ that goes into $ab$ and $c$, so $ab=px$ and $c=py$. but now what?? I tried $abc=p^2xy$ but then I can't. Please help me!
0
votes
2answers
64 views

Let $a$ and $b$ be positive integers and let $p$ be a prime number. Prove that if $a^p \equiv$ $b^p$ (mod $p$), then $a \equiv b$ (mod $p$).

I am trying to solve the following problem: Let $a$ and $b$ be positive integers and let $p$ be a prime number. Prove that if $a^p \equiv$ $b^p$ (mod $p$), then $a \equiv b$ (mod $p$). My attempt to ...
1
vote
1answer
26 views

Proof that there are at the most two numbers of exactly six digits that squared end with the same six digits

Written in a more formal way, proof that there are at the most $2$ numbers $n$ of six digits, that $$n^2 \equiv n \mod 10^6$$ Research effort: if $n^2 \equiv n \mod 10^6$ this means $10^6\mid ...