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

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

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
25 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
38 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$ ...
3
votes
5answers
119 views

How to show $n(n+1)(2n+1) \equiv 0 \pmod 6$?

I've been asked to show that: $n(n+1)(2n+1) \equiv 0 \pmod 6$ I found in a previous question that: $n(n+1)$ was divisible by $2$ and resulted in an even number e.g $n(n+1) \equiv 0 \pmod 2$ so I ...
2
votes
1answer
49 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
1answer
122 views

How to understand Apostol's proof of the irrationality of $\sqrt{n}$ if $n$ is not a perfect square?

Recently I am reading the textbook of Apostol, Mathematical Analysis, Second Edition. On page 7, there is a theorem 1.10: If $n$ is a positive integer with is not a perfect square, then $\sqrt{n}$ is ...
0
votes
0answers
34 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
42 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
42 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
27 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 ...
5
votes
5answers
630 views

Divisibility by 7

What is the fastest known way for testing divisibility by 7? Of course I can write the decimal expansion of a number and calculate it modulo 7, but that doesn't give a nice pattern to memorize because ...
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
34 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
0answers
39 views

Greatest common divisor / euclidean algorithm linear combination proof

Consider integers $m$ and $n$, not both 0. Show that gcd$(m,n)$ is the smallest positive integer that can be written as $am + bn$ for integers $a$ and $b$. I'm confused on what exactly to do--I'm ...
1
vote
1answer
56 views

Using Extended Euclidean Algorithm

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$. I have ...
0
votes
1answer
28 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 ...
2
votes
2answers
48 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
vote
0answers
25 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: $$ ...
0
votes
1answer
52 views

WordProblem on factors and remainder theorem

Mr.Chaalu while travelling by Ferry queen has travelled the distance one Kilometer more, than the fare he paid per km. Initially he had total amount of Rs.350/- in his wallet. Now he is only left with ...
-1
votes
2answers
26 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?
8
votes
4answers
117 views

g.c.d.{$m^p-m:m=2$ to $n$} $= ?$

Let $p$ be an odd prime and $n>2$ is an integer , then what is the $g.c.d.$ of the numbers {$m^p-m:m=2$ to $n$} ? (by Fermat's little theorem it is easy to see , $2p$ divides the g.c.d. , but I can ...
-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
1answer
40 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
78 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
15 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)$$
2
votes
0answers
22 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}$. ...
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
4answers
47 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
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 ...
1
vote
1answer
44 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
17 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
45 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
23 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$? ...
1
vote
2answers
54 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
0answers
11 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
43 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.: ...
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
29 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
27 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 ...
60
votes
12answers
16k views

Dividing 100% by 3 without any left

In mathematics, as far as I know, you can't divide 100% by 3 without having 0,1...% left. Imagine an apple which was cloned two times, so the other 2 are completely equal in 'quality'. The totality ...
0
votes
2answers
51 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 ...
1
vote
4answers
1k views

What is the remainder when 4 to the power 1000 is divided by 7

What is the remainder when $4^{1000}$ is divided by 7? In my book the problem is solved, but I am unable to understand the approach. Please help me understand - Solution - To find the ...
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 ...
1
vote
1answer
140 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 ...
0
votes
2answers
38 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
28 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
28 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$ ...