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
134 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
52 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
39 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
37 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
38 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 ...
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
156 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
46 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
85 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
130 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
40 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
87 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}).$$
1
vote
2answers
100 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 ...
1
vote
0answers
84 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
64 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 ...
1
vote
3answers
41 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
34 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
21 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
81 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
89 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
2answers
19 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$. ...
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
vote
2answers
68 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
1answer
23 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
5answers
41 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 ...
0
votes
1answer
36 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 ...
1
vote
1answer
25 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
45 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 + ...
6
votes
9answers
315 views

If n is a positive integer, then $n^3 + 5n$ is divisible by $6$. [duplicate]

Is this possible to prove through the induction method. It seems it is not to me. I built a base case, proceeded to substitute in k, then finally moved onto my $k+1$ case. Where I ended up with a ...
1
vote
3answers
72 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
40 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.
1
vote
4answers
164 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 ...
4
votes
2answers
120 views

Primes $p$ such that $p^2$ divides $x^2 + y^2 + 1$

Call a prime $p$ awesome if there exist positive integers $x$ and $y$ such that $p^2$ divides $x^2+y^2+1$. Observation: $2$ is not awesome, because $x^2+y^2+1\not\equiv 0$ (mod $4$). But $3$ is ...
2
votes
3answers
77 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
42 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 ...
7
votes
1answer
89 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
23 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
86 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
51 views

Using long division on polynomials

Can anyone show me how to find $x^5 + 1$ divided by $x^3 + 1$?
2
votes
2answers
77 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!
2
votes
2answers
41 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 ...
0
votes
2answers
130 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
27 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 ...
1
vote
1answer
49 views

Help with proving bezout's theorem?

Let $a,b,c\in\mathbb Z$ where $d=\gcd(a,b)$ and $c$ is a multiple of $d$. Suppose that $(x=x_0, y=y_0)$ is one particular integer solution to $$ax+by=c.$$ Then the complete set of integer ...
3
votes
3answers
127 views

how to prove if $m^{2}|n^{2}$ then m|n just hint please. [duplicate]

How to prove the following?: Let $m,n\in \mathbb{N}$ ; $ \;m^{2}\mid n^{2}\Longrightarrow \;\;m\mid n$ Just a hint please. I tried two ways but did not work.
0
votes
3answers
54 views

Number Theory: Remainders

“ Let $a, b \in \mathbb{Z}$ and that $0<a<b$. Given $b=qa+r$ where $0\leq r<a$. Prove that $r$ is always less than $\frac{b}{2}$. ” I have played around with several examples and have ...
4
votes
2answers
39 views

Find all the polynomials $p \in \mathbb R [X]$ such that $(x+1)p=(p')^2$

(Where $p'(x)$ is the derivative of $p(x)$) Research effort: what I thought is that given that $(x+1)|(p')^2$ then $(x+1)|(p')$ (I'd like to justify better this, but I don't know how) Then, ...
0
votes
1answer
20 views

A conjecture about the existence of a member within an interval with certain divisibility conditions - counter examples?

Conjecture The interval of the natural number line $[ap_{n}, (a+1)p_{n}]$ contains a member $e$ that is not divisible by any prime number $p_{m}$ less than or equal to $p_{n}$, if $(a+1) \leq ...
0
votes
1answer
75 views

An easy question with integer numbers

I have an easy question of arithmetic. Let $a, b, N$ be integer numbers such that $\mathrm{gcd}(a,b,N) = 1$. Is it true that there exists an integer number $x \in \mathbb{Z}$ such that ...
1
vote
1answer
38 views

Divisibility problem with product of two primes

Be $n=pq$ a natural number product of two different primes $p,q$. Prove, that on the set $\{1.2,2.3,...,n(n+1)\}$ there are exactly 4 numbers divisible by $n$.