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
1answer
14 views

Lowest divisible number in number string

A number is arranged in a pattern like: 12345678910111213141516... What is the lowest value of that pattern divisible by 72? They are single numbers, not seperate (i.e. first in sequence is 1, ...
2
votes
0answers
18 views

To calculate what is $\sum_{1 \le m<n ;(m,n)=1} m^2$ or what is the remainder when $\sum_{1 \le m<n ;(m,n)=1} m^2$ is divided by $n$?

For an integer $n >1$ , what is the sum of the squares of all the positive integers that are less than $n$ and relatively prime to $n$ that is I am trying to calculate $f(n):=\sum_{1 \le m<n ...
2
votes
2answers
42 views

Prove if $3$ does not divide $n$, then $n^2=1+3k$ for some integer $k$

I am proving by cases but am getting confused. I am not sure if this leads to a contradiction or not. Here's what I have so far: Direct Proof. Suppose $3$ does not divide $n$. Case 1: remainder ...
5
votes
4answers
88 views

Prove that $13\vert(3^{n+1} +3^{n} +3^{n-1})$

Prove that $3^{n+1} +3^{n} +3^{n-1}$ is divisible by $13$ for all positive integral values of $n$
1
vote
2answers
42 views

Finding zeroes of $x^3-5x^2+11x+17$

I'm trying to find all the zeros of $x^3-5x^2+11x+17$. I figured the possible zeros as being +/- 1, +/- 17$. The book says that -1 is supposed to be a factor, but I tried dividing the polynomial by ...
3
votes
3answers
80 views

prove by induction that $29^n - 21^n$ is always divisible by $8$

I have to prove by induction that that $\forall n \in N,$ $8 | (29^n - 21^n) $ . I understand how to prove things with induction generally, but im not sure where to even start with this one. I ...
0
votes
2answers
17 views

GCD proof using fundamental theorem of arithmetic

prove: $\gcd(m,n)=1$ if and only if $\gcd(m^i,n^r)=1$ I believe you need to do something with fundamental theorem of arithmetic to prove one of the sides. Not quite sure though. Help is appreciated. ...
1
vote
3answers
58 views

Are there in pure mathematics ensembles of number's which not divided by them self except $0$?

In pure mathematics we know well that each number divided by him self except $0$ , the question that let me confused is: Is there a proof in pure mathematics show to us that there are others ...
7
votes
1answer
62 views

If two elements a,b have a gcd, do then a*t,b*t also have a gcd?

Let $M$ be a commutative cancellative monoid. For elements $a,b \in M$ a gcd of $a,b$ is an element $\mathrm{gcd}(a,b)$ with the (universal) property $\forall c \in M (c |\mathrm{gcd}(a,b) ...
0
votes
1answer
19 views

Finding the number that gives remainder equal to 0

Hi i'm not english so I'll try to explain this as good as I can . If we have for example 250 : 5 = 50 , remainder 0 let's say I don't know the number i'm going to divide (because it is generated ...
-3
votes
2answers
39 views

How to show $a c\equiv bc\pmod{n}$ where $n \ge 2$ does not imply $a \equiv b \pmod n$? [on hold]

How to show $a c\equiv bc\pmod{n}$ where $n \ge 2$ does not imply $a \equiv b \pmod n$? Would it be possible for someone to go over this step by step?
1
vote
1answer
22 views

Proving n is not divisble by m using Division Algorithm

When $n$ and $m$ are integers, how could I write a statement equivalent to the statement "$n$ is not divisible by $m$" using ideas from the Division Algorithm?
1
vote
4answers
36 views

If $(a,c)=1$ and $(b,c)=1$, prove $(ab,c)=1$.

I'm posed with the problem in the title, Let $a,b,c\in\mathbb{Z}$. Then if $(a,c)=1$ and $(b,c)=1$, prove $(ab,c)=1$. (By the way, $(a,c)=1$ means that the greatest common divisor of $a$ and $c$ ...
-1
votes
1answer
23 views

Show that a·c ≡ b·c (mod m) with a, b, c and m integers with m≥2 does not [3] imply a ≡ b (mod m) [on hold]

I'm working through some practice problems but I am having some trouble understanding this question and was wondering if it'd be possible for someone to help me go over it step by step. Thanks
2
votes
1answer
36 views

Finding the number of divisible integers in the range $[1, 1000]$.

Sorry if this is a stupid question. I am asked to find the number of positive integers in the range $[1, 1000]$ that are divisible by $3$ and $11$ but not $9$. Here's how I $\text{tried}$ to do it. ...
0
votes
0answers
25 views

Round table and division of numbers, need proof.

Let's assume that k-number of people are sited on a round table (k>=2). Each of them chooses a card with a number from 1 to n where n>=k. Each card has a different number (2 people can't pick a card ...
1
vote
1answer
37 views

synthetic division with $i$ in divisor

I divided $x^3-4x^2+4x-16$ by $-2i$ using synthetic division and got a remainder of $-8i-8$. Is that right? I'm not sure I'm doing this right.
1
vote
2answers
37 views

Maximum GCD of two polynomials

Consider $f(n) = \gcd(1 + 3 n + 3 n^2, 1 + n^3)$ I don't know why but $f(n)$ appears to be periodic. Also $f(n)$ appears to attain a maximum value of $7$ when $n = 5 + 7*k $ for any $k \in \Bbb{Z}$. ...
0
votes
1answer
26 views

Solve denominator so quotient is whole number?

I have a simple equation. road_length = ROADLENGTH / ROADSPACING The problem is, I really need road_length to be a whole number because it's used in FOR loop in ...
0
votes
2answers
16 views

Prime Factorizations that divide each other

Let n have prime factorization n = p^s1 · p^s2 · · · p^sk and let m have prime factorization m = q^t1 · q^t2 · · · q^tl If n|m, what must be true about the corresponding lists of primes and the ...
1
vote
3answers
27 views

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$ Should I prove this by induction? If so, how should I go about it?
0
votes
1answer
26 views

Understanding Bézout's identity's proof as given on wikipedea.

I am reading this proof of Bézout's identity. It starts as: For given nonzero integers $a$ and $b$ there is a nonzero integer $ax + by$, $x$ and $y$ are also integers. The minimum absolute value of ...
1
vote
0answers
24 views

On counting number pairs having a specific greatest common divisor.

I wanted to count natural numbers $k$ not exceeding the fixed $n \in \mathbb{N}$ and having a greatest common divisor $\gcd(n,k) = d$ naturally for some $d \mid n$. In more mathematical terms: $$ ...
2
votes
2answers
45 views

A question on divisibility

For what values of $x,y \in \{1,2,3,...9 \}$, does $$10x+y \space\mid 100x + y $$ ? What approach should I take for solving this problem ?
-1
votes
1answer
18 views

need help with equasion

Well. My computer has fritzed up and I'm having to perform some lenghy task, it's processing 20 files every 2 seconds, it's at 459000 of 854528 Roughly how long in seconds might it take? I've ...
0
votes
2answers
21 views

GCD of polynomials in $\mathbb{F}_2[x]$

How can one show that $\gcd(x^4+x+1,x^4-x)=1$ in $\mathbb{F}_2[x]$? Is it because the polynomials do not share any irreducible monic polynomials i.e. $1, x, x+1$ as factors?
0
votes
1answer
39 views

gcd of polynomials over Z_7

I want the gcd of the two polynomials: $$f=x^5+3x^4+5x^3+x^2+x+3$$ $$g=2x^3+4x^2+x$$ in $Z_7[x]$. My approach: I use the euclidean algorithm and continue until I get no remainder. ...
5
votes
2answers
73 views

$a+b+c+d+e$ divides $a^5+b^5+c^5+d^5+e^5-5abcde$

Let $a,b,c,d,e$ be integers such that $a(b+c)+b(c+d)+c(d+e)+d(e+a)+e(a+b)=0$. Prove that $a+b+c+d+e$ divides $a^5+b^5+c^5+d^5+e^5-5abcde$. I'm reminded of the factorization ...
1
vote
1answer
13 views

GCD of polynomials by using Euclid's algorithm

Let $g = x^2 +6x -7$ and $f = x^4 - 1$. Find the GCD of $f$ and $g$. So I started by evaluating $f/g$ and the result is $q = x^2-6x+43, r = -300x+300$. I tried to follow the algorithm one step ...
0
votes
2answers
26 views

$c=\text{gcd}(a,b)$ means $\exists{x,y}\in{\mathbb{Z}}$ so that $a=cx$ and $b=cy$. Show $\text{gcd}(x,y)=1$

Obvious homework question, so hints please: Suppose $a,b \in{\mathbb{Z}_+}$ and $c=\text{gcd}(a,b)$. So we know $\exists{x,y}\in{\mathbb{Z}}$ so that $a=cx$ and $b=cy$. Show that ...
0
votes
3answers
45 views

Prove that $\gcd(ab,m)\mid\gcd(a,m)\gcd(b,m)$ [closed]

Prove that if $a,b,m\in\mathbb N\setminus\{0\}$, then $$\gcd(ab,m)\mid\gcd(a,m)\cdot\gcd(b,m)$$
0
votes
2answers
52 views

Prove that $a$ is odd if and only if there exists $p$ such that $a = 2p +1$ [closed]

$a$ is odd if and only if there exists a $p$ such that $a = 2p +1$. I've realized I have to apply the division algorithm, $m = q\cdot n +r$, but I can't figure out how. Any help is appreciated.
2
votes
0answers
21 views

How do I know the cyclic subgroups of G generated by a are equal?

I had a question of understanding that I was hoping you guys could help me with. Suppose there exists a group in the integers. For the sake of my understanding, let's say the group is, G = $Z_{60}$. ...
1
vote
4answers
46 views

Prove that if $a$ divides $ b$ , and $a$ divides $b + 2$ then $a = 1$ or $ a = 2$.

For positive integers $a,b$, prove that if $a$ divides $b$ and $a$ divides $b + 2$ then $a = 1$ or $a = 2$. I know that if $a|b$ and $a|c$ then $a|b+c$ or $a|b-c$ but I can't figure out how to get ...
1
vote
1answer
38 views

greatest common divisor proof

I have two questions about a prove that I have to do for my mathematic study. I'm now thinking about it the whole day, but can't find the prove. Let $a,b \in \mathbb Z_{>0}$. (a) Prove: $\gcd(2^a ...
0
votes
1answer
15 views

Number theory,GCD, coprime integers

I am sorry for the bad title but I really can't think of a better one. So I was learning about the euclidean algorithm and I see a statement that is hard for me to understand. In the book that I was ...
1
vote
1answer
34 views

How to find the number of divisors that are perfect squares and divisible by a number

Suppose $ n = 2^{14} 3^{9} 5^{8} 7^{10} 11^{3} 13^{5} 37^{10} $ , find the number of positive divisors that are both perfect squares and divisible by $ 2^{2}3^{4}5^{2}11^{2}$. It is quite simple to ...
0
votes
0answers
22 views

Need help with GCD, and Euclid algorithm

Okay, So I was given a worksheet to work through. I already got the solutions but I still don't get it. I already understood Q10, and the solution basically said that Q11 is connected with Q10. But ...
1
vote
0answers
40 views

If p is a prime what values of $ a\leq p^{n}$ have $\text{gcd}(a, p^{n}) >1$?

Hi guys need your help. Sorry but I don't understand how to use latex. So really sorry for the writing. The question is if p is prime what values of $ a\leq p^{n}$ have $\text{gcd}(a, p^{n}) >1$? ...
0
votes
0answers
10 views

synthetic division for find function answer reasoning

Why use synthetic division to find, say f(5), when you could just plug in 5 in place of all the x in the function and solve directly? Is there something more to this? Do some people just find it ...
0
votes
1answer
42 views

Proof about relation between the least common multiple and the greatest common divisor

What's the simplest proof that the least common divisor of $a$ and $b$ is equal to the product of $a$ and $b$ divided by the greatest common divisor, i.e.: ...
1
vote
3answers
44 views

Strategy for solving $7\vert2^{n+2}+3^{2n+1}$ by induction.

So I have to show the following to be true using induction $7\mid 2^{n+2}+3^{2n+1}$ This is easily checked with the case $n=0$ because $7 \mid 7$, but I assuming this holds for$n=k :$ $$7\mid ...
0
votes
0answers
27 views

Prove that $p^r\mid xp^r-p^{r-1}-1$

If $p$ is a prime integer and $x$ is prime to $p$, show that $p^r\mid xp^r-p^{r-1}-1$. I have tried with the following steps: $$p^r\equiv 0\pmod{ p^r}\implies xp^r\equiv 0\pmod{p^r}.$$ How can I ...
1
vote
2answers
27 views

Proof by Induction: for all integers n $\ge$ 0, $12\mid8^{2n+1}+2^{4n+2}$

I'm working on a homework problem for my discrete math class, and I'm stuck. (Note: I made a post about this earlier, but I read the problem incorrectly, thus the work was wrong, so I deleted the ...
4
votes
1answer
25 views

Is there an $n$ such that $p|n^2+1$ with $2n<p<2n+\sqrt n$?

Is there an integer $n$ such that $n^2+1$ is divisible by a prime $p$ with $2n<p<2n+\sqrt n$? It's complicated to describe my interest, but these are near-missed for arc-cotangent reducible ...
0
votes
2answers
29 views

Prove divisibility

We have the following proposition: $$P(n): 13^n+7^n-2\vdots 6$$. Prove $P(n)$ in two ways. I know that one of them is mathematical induction. I don't know many things about the other one, I know ...
1
vote
2answers
47 views

Divisibility problem using DFA

Original problem: Create a DFA for every positive integer $k$, so that when DFA takes a binary string (reading from most significant bit), decides whether the number is divisible by $k$. A DFA for a ...
0
votes
2answers
50 views

Proving a polynomial is not divisible

Let $k\geq2$ be even and let $f(x)=x^{k}+x^{k-1}+...+1\in\mathbb{Q}[x]$ I want to prove that there is no linear polynomial that divides $f(x)$ So I figured that if there was $g(x)=x-\alpha$ that ...
5
votes
3answers
44 views

Divisors $1\bmod 4$ more than $3\bmod 4$

For any positive integer $n$, let $f(n)$ denote the number of positive divisors of $n$ which are $1\bmod 4$, and $g(n)$ denote the number of positive divisors of $n$ which are $3\bmod 4$. Is it true ...
2
votes
0answers
19 views

Does this expression involving GCDs simplify?

I've run into a strange thing: $$\gcd\left((a^2+c^2)(b^2+c^2),4c \gcd\left( a(b^2 + c^2), b(a^2 + c^2), 2a b(a + b) \right) \right)$$ Given that $1 =\gcd(a,b,c)$, does the above complicated-looking ...