Tagged Questions

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)

5
votes
0answers
28 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
15 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
38 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
17 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
35 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
22 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
35 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
18 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
24 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
34 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
25 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
15 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
24 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
23 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
42 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
1answer
57 views

how do i do this question? [closed]

Express the greatest common divisor of these pair of integers as a linear combination of the integers: 9999 and 11111
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)$$
1
vote
2answers
51 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
37 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
43 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
26 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
24 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
46 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 ...
0
votes
2answers
36 views

Weak Mathematical Induction for Modulo Arithmetic

Using Weak Mathematical Induction, I have to show that, for all integers $n \geq 1$, $8|3^{2n} -1$ I really don't know how to go about solving this problem. Currently I only have the base case and ...
0
votes
1answer
27 views

Basic question on Number Theory and Divisibility

Prove or disprove that if $a\mid(sb + tc)$ for all $s,t$ elements of integers, then $a\mid b$ and $a\mid c$ My question is "for all". I'm clearly misunderstanding something, because my intuition is ...
1
vote
1answer
25 views

Proof with greatest common divisors

I'm learning about properties of greatest common divisors, specifically when two numbers are relatively prime. The exercise I'm working through is : Suppose that $\gcd(a,b) = 1$ and that $a\mid n$ ...
1
vote
1answer
137 views

question about cryptography

Sam and Tim have set up their RSA keys (eS; n); (eT; n), respectively, where the n-value is the same. Furthermore, it happens that gcd(eS;eT) = 1. Suppose that their friend Rob wants to send both Sam ...
5
votes
0answers
64 views

Product of consecutive Fibonacci numbers divisibility

Prove that the product of any $k$ consecutive Fibonacci numbers is divisible by the product of the first $k$ Fibonacci numbers. We can try to show that for every prime $p$, the power of $p$ appearing ...
0
votes
2answers
25 views

divisibility relation $a|b^2 + 10c.$

Use divisibility relation to show that for all integer $a$, $b$, $c$, $a \ne 0$ counts if $a|b$ and $a|c$ then $a|b^2 + 10c$. Use direct proof. Ok, $a|6$ then there is integer $k$. $$a*k=6,$$ ...
0
votes
0answers
28 views

Find all $s,t$ such that $sa+tb=0$ in PID

I am stuck on this problem: Let $R$ be a PID. Fix $a,b\in R$. Define $f:R\times R\rightarrow R$ by $f(s,t)=sa+tb$. Determine ker$f$ explicitly: Show that there exists a function $g:R\rightarrow ...