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
103 views

Prove Divisibility test for 11 [duplicate]

Prove Divisibility test for 11 "If you repeatedly subtract the ones digit and get 0, the number is divisible by 11" Example: 11825 -> 1182 - 5 = 1177 1177 -> 117 - 7 = 110 110 -> 11 - 0 = 11 11 ...
2
votes
2answers
73 views

Prooving by absurd that $d \nmid 4,5,10, 20$

What I'm trying to solve is the following: Given that $(a:b) = 2$, proove that $(a^2 + 2b^2+10:20) = 2$. So, basically, I think that what I need to do is to show that if $d = a^2 + 2b^2 + 10$, then ...
0
votes
2answers
177 views

Given that $gcd(a,b)=1$, prove that $gcd(a+b,a^2-ab+b^2)=1$ or $3$, also when will it equal $1$? [duplicate]

It is an exercise on the lecture that i am unable to prove. Given that $gcd(a,b)=1$, prove that $gcd(a+b,a^2-ab+b^2)=1$ or $3$, also when will it equal $1$?
0
votes
1answer
55 views

finding factors for gcd

To compute $gcd(25, 11)$, Euclid's algorithm would proceed as follows: $$\underline{25} = 2 \cdot \underline{11}+3$$ $$\underline{11} = 3 \cdot \underline{3}+2$$ $$\underline{3} = 1 \cdot ...
0
votes
1answer
72 views

Prove divisibility for general equation of sucession

I have the following problem: Prove that given the following succession: $a_1 = 2, a_2 = 4, a_{n+2} = (n+1)a_{n+1} + (n-1)a_n, \forall n \in \mathbb{N}$ then, it follows that $\forall n \in ...
1
vote
3answers
72 views

Divisibility of a prime number

I need help with the following: Show that: If $p$ is prime such that $p$ divides $a^n$ Then $p^n$ divides $a^n$ I know that if $p$ is a prime and divides a square number $a$ then $p$ also ...
0
votes
1answer
69 views

Find Greatest Common Divisor and Least Common Multiple

Find GCD (320, 112) and LCM[320, 112]. Solve the equation 320x + 112y = a in the following situations: (i) a = 32 (ii) a = 10. Using Euclids Algorithm to find the GCD I have the following: ...
2
votes
5answers
371 views

Show that the sum of squares of four consecutive natural numbers may never be a square.

Show that the sum of squares of four consecutive natural numbers may never be a square. I know (and I have the proof) a theorem that says that every perfect square is congruent to $0, 1$ or $4$ ...
4
votes
4answers
199 views

Find the smallest natural number that leaves residues $5,4,3,$ and $2$ when divided respectively by the numbers $6,5,4,$ and $3$

Find the smallest natural number that leaves residues $5,4,3,$ and $2$ when divided respectively by the numbers $6,5,4,$ and $3$. I tried ...
0
votes
3answers
102 views

If $ a|n$ and $b|n$ and $\gcd(a, b) = 1$ then $ab|n$

This is an extremely simple problem but I'm new to this sort of math so I was wondering if anyone could lead me in the correct direction as to how I'd prove this formally?
9
votes
1answer
548 views

Does $n \mid 2^{2^n+1}+1$ imply $n \mid 2^{2^{2^n+1}+1}+1$?

There are two ways to try to prove this. One is in the title, the other is its de Morgan counterpart: $n \nmid 2^{2^{2^n+1}+1}+1 \implies n \nmid 2^{2^n+1}+1$. Disproving it requires only one example ...
0
votes
1answer
30 views

Given a set of numbers $x_1, x_2, \ldots, x_k$, what is the largest number $h$ such that $x_i \bmod{h} = 0$ for all $i$?

I am solving a system of differential equations with respect to length, let's say 0 to $x_{max} = 10$ meters. Now, I want to choose an integration step such that my step will land on each of the ...
-1
votes
1answer
52 views

Demonstration, $70\mid 101^{6n}-1\;\;\forall n\in\mathbb{N}$ [closed]

$70\mid 101^{6n}-1\;\;\forall n\in\mathbb{N}$ Demonstration: $$101\equiv 31\pmod{70}\\101^2\equiv31^2\equiv961\equiv51\pmod{70}\\101^{6}\equiv51^2\equiv2601\equiv11??$$
0
votes
0answers
30 views

the division $14^{256}$ by $17$ [duplicate]

What the rest of the division $14^{256}$ by $17$? $$14^2\equiv9\pmod{17}\\14^4\equiv13\pmod{17}\\14^8\equiv16\equiv-1\pmod{17}\\(14^8)^{32}\equiv(-1)^{32}\equiv1\pmod{17}$$The rest is $1$, ...
7
votes
3answers
133 views

centenes of $7^{999999}$

What is the value of the hundreds digit of the number $7^{999999}$? Equivalent to finding the value of $a$ for the congruence $$7^{999999}\equiv a\pmod{1000}$$
3
votes
1answer
81 views

Prove that $x^4+x^3+x^2+x+1 \mid x^{4n}+x^{3n}+x^{2n}+x^n+1$

Problem: Prove that $x^4+x^3+x^2+x+1$ divides $x^{4n}+x^{3n}+x^{2n}+x^n+1$ for all positive $n$ that are not multiples of $5$. I'd like to get some pointers about how to solve this. No full ...
0
votes
2answers
96 views

To prove $6|σ(6n-1) , ∀n∈ \mathbb N$

Let $σ(n)$ denote the sum of all the positive divisors of $n∈ \mathbb N$. I think that $6$ divides $σ(6n-1)$ for all $n∈ \mathbb N$ , but I am not able to prove it. So, a proof of the result (if it ...
3
votes
0answers
67 views

Find the fundamental group and the Alexander polynomial

I would like to find the Alexander polynomial of the link $L$, described below. Let $K(q,r)$ be the $(q,r)$-torus knot embedded on a torus $V$. Inside the torus $V$, consider a smaller solid torus ...
0
votes
2answers
162 views

calculate GCD of very large integers

How i can calculate GCD of two very large integers for example: gcd(31415926534676736647, 438478473847834834784748) either by hand or computer? is there any ...
2
votes
3answers
2k views

Find the sum of all the integers between 1 and 1000 which are divisible by 7

How can I work this one out (with workings)? "Find the sum of all the integers between 1 and 1000 which are divisible by 7" Thanks!
5
votes
2answers
325 views

Prove that if $gcd(a,b)=1$, then $gcd(a^2,b^2)=1$

So, if $gcd(a,b)=1$, then $gcd(a^2,b^2)=1$ means $1=ax+by$, and want to show $a^2x+b^2y=1$. By squaring $1=ax+by$ both sides, I get, $1=(ax)^2+b(2axby+by^2)$. It doesn't help my proof. Please help me ...
0
votes
1answer
57 views

Prove $gcd(a-1,a+1)$

Let $a$ be an integer. After looking at several examples, make a conjecture about the value of $gcd(a-1,a+1)$ and prove it. Ok, I found if $a$ is even, $gcd(a-1,a+1)=1$, if $a$ is odd, ...
0
votes
4answers
104 views

Need to prove that $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5$ is divisible by $99$ for all $n \in \mathbb{N} $, using induction.

First, obviously, I figured out the base case. So I have $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5 = 99k$ for some $k \in \mathbb{N} $. As for the inductive step, I was thinking about splitting it up ...
1
vote
3answers
32 views

For every integer $a$, if $a \not\equiv 0\pmod3$, then, $a^2\equiv 1\pmod3$.

It is always confusing to prove with $\not\equiv$. Should I try contrapositive?
1
vote
5answers
63 views

Prove if $a\mid b$ and $b\mid a$, then $|a|=|b|$ , $a, b$ are integers.

Form the assumption, we can say $b=ak$ ,$k$ integer, $a=bm$, $m$ integer. Intuitively, this conjecture makes sense. But I can't make further step.
1
vote
1answer
90 views

GCD of two numbers

Let us call the largest common divisor of integers $m$ and $n$ by $(m,n)$. For example, $(2,3)=1$ and $(10,15)=5$. Let us assume that $n(n+1)(n+2)$ is a square where $n$ is an integer. Now I want to ...
3
votes
3answers
534 views

Use mathematical induction to prove that 9 divides $n^3 + (n + 1)^3 + (n + 2)^3$; Looking for explanation, I already have the solution.

I have the solution for this but I get lost at the end, here's what I have so far. basis $n = 0$; $9 \mid 0^3 + (0 + 1)^3 + (0 + 2)^2 ?$ $9 \mid 1 + 8$ = true Induction: Assume $n^3 + (n + ...
2
votes
1answer
79 views

Show that there exist infinitely many primes of the form $6k-1$

This is a question on the text book that i have no way to deal with. Can anyone help me? Show that there exist infinitely many primes of the form $6k-1$
1
vote
2answers
130 views

Divisiblilty & Prime Problems [GRE]

if j is divisible by 12 and 10, is j divisible by 24? Answer by either saying yes, no , or Can't be determined. I approached this question as follow: First i found the prime factors of both ...
6
votes
2answers
129 views

Divisibility of Fibonacci numbers

This question is inspired by a Project Euler problem I was working on. Noticing something that did not make sense led me to the conclusion that for all primes $p$ ending in $1$ or $9$, the $(p-1)$st ...
1
vote
1answer
38 views

Integral domain is ufd iff atomic and gcd domain

an Integral domain D is a UFD if and only if D is atomic and gcd domain. I know that a UFD is Atomic, but i don't know how to prove it is a gcd domain. the other side of the proof: I do understand ...
0
votes
2answers
66 views

How to find the remainder of $(2010^{1020} + 1020^{2010})$ divided by $3$

What is the remainder when $2010^{1020} + 1020^{2010}$ is divided by 3?
0
votes
0answers
184 views

Smallest positive integer divisible by and having digit sum equal to some 3-digit number.

Let $p,q,r$ be distinct digits among $1,2,4,6,8$, and consider the integer $pqr = 100p + 10q + r$. Let $N$ be the smallest positive integer that is divisible by $pqr$ and has digit sum equal to ...
2
votes
1answer
73 views

Number of prime divisors in an interval

I've found a problem on a c++ website and I don't know how to solve it. Given an interval [x,y] and a number K I have to find how many numbers from this interval have exactly K distinct prime ...
2
votes
1answer
208 views
3
votes
1answer
75 views

Proof that $n+1$ divides $\sum_{k=1}^n k^q$ for $q > 0$

Since $$\sum_{k=1}^n k = \frac{n\left(n+1\right)}{2}$$ $$\sum_{k=1}^n k^2 = \frac{n\left(n+1\right)\left(2n+1\right)}{6}$$ $$\sum_{k=1}^n k^3 = \frac{n^2\left(n+1\right)^2}{4}$$ ... and so on. Is ...
3
votes
1answer
76 views

Divisibility involving root of unity

Let $p$ be a prime number and $\omega$ be a $p$-th root of unity. Suppose $a_0,a_1, \dots, a_{p-1}, b_0, b_1, \dots, b_{p-1}$ be integers such that $a_0 \omega^0+a_1 \omega^1+ \dots a_{p-1} ...
8
votes
3answers
155 views

How can we find the gcd for elements (binomial coefficient)?

$\gcd\left(\binom{2n}1,\binom{2n}3,\binom{2n}5,\ldots,\binom{2n}{2n-1}\right)$ i want to know what is specialty of such a series.I am not able to generalize the problem solution.Is there any rule for ...
1
vote
3answers
28 views

Division by fractions [duplicate]

Why is it that to divide by a fraction you need to multiply by the reciprocal of that fraction? For instance: $\eqalign{ & 1 \div \frac{1}{3} \cr & = 1 \times 3 \cr & = 3 ...
4
votes
1answer
133 views

Solve $a^3 + b^3 + c^3 = 6abc$

Find solutions for $a^3 + b^3 + c^3 = 6abc$ in $\mathbb{N}$, such that $gcd(a,b,c) = 1$, except for $(1,2,3)$ and its permutations. Using trial and error I found out that if $a,b,c$ are solution ...
2
votes
1answer
66 views

A problem relying on van der Waerden's theorem, and the existence of sums divisible by a given number $n$

Say we are given a sequence of integers $\{a_i\}_{i \in \mathbb{N}}$, as well as a pair of integers $n, m$. How can we show that there always exist positive integers $s, r$ such that the sums $a_s + ...
1
vote
1answer
186 views

Proof verification on Fermat's Little Theorem exercise - new way to solve problem?

I don't know if I'm correct, since I didn't even have to use the hint. So I'm asking for proof verification since I am also not too confident on primes. Suppose $\gcd(a, 35) = 1.$ Show that ...
3
votes
1answer
53 views

Solving $\frac{{2{x^3} - 11x + 6}}{{x - 2}}$ using algebraic juggling

Answer: $\eqalign{ & \frac{{2{x^3} - 11x + 6}}{{x - 2}} = \frac{{2{x^2}(x - 2) + 4{x^2} - 11x + 6}}{{(x - 2)}} \cr & = 2{x^2} + \frac{{4x(x - 2) - 8x + 11x + 6}}{{x - 2}} \cr ...
1
vote
2answers
82 views

Distribution of primes remainders

Naively, I would expect the natural density the number of a fixed prime $p$ with remainder $m$ to the other primes to be uniform $$ d(p,m) = \limsup\limits_{n\rightarrow\infty} \frac{a(n,m)}{n} = ...
0
votes
1answer
52 views

Divisibility question with 8th powers

so I was assigned a divisibility question for homework. Prove that $27195^8-10887^8+10152^8$ is divisible by $26460$. Am I supposed to use mods? I appreciate the help!
0
votes
2answers
31 views

Divisibility of a power

I'm being asked to prove that if $n|m$ and $a > 1$ then $\frac{a^m-1}{a^n-1}$ is an integer. I would like an algebraic prove of the problem.
3
votes
4answers
91 views

Prove $5 | 2^{n+1} + 3^{3n+1}$

I tried induction, so I assume the hypothesis and attempt to show $5 | 2^{n+2} +3^{3n + 4}$ but this doesn't help. I tried breaking it down into prime factorizations, but I do not see it.
2
votes
2answers
54 views

Divisibility and factorial

If $n = st$ and $s > 0$ and $t > 0$ then prove that $(s!)^t|n!$ . If I replace $n!$ with $ (st)!$ how can I simplify it so that I can show that the division is an integer.
3
votes
1answer
99 views

Relationship between divisibility of polynomials and divisibility of its evaluations

Let $f$ and $g$ be primitive polynomials over $\mathbb{Z}$. Decide if the following is true: $f(x) \mid g(x)$ for infinitely many $x\in\mathbb Z$ implies $f\mid g$ as polynomials in ...
1
vote
1answer
42 views

Values of $gcd(a-b,\frac{a^p-b^p}{a-b} )$

I don't know how to prove the following result. Let $p$ be a prime number and let $a,b \in \mathbb Z$ such that $gcd(a,b)=1$ Then $gcd(a-b,\frac{a^p-b^p}{a-b}) = 0 $ or $ p $ I know that ...