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)

2
votes
1answer
32 views

Find the greatest positive integer $x$ such that $23^{6+x}$ divides $2000!$

I'm currently reading Andreescu and Andrica's Number Theory: Structures, examples and problems. Problem 1.1.7 states : Find the greatest positive integer $x$ such that $23^{6+x}$ divides $2000!$. The ...
3
votes
5answers
176 views

What does “$x$ divides $y$” mean?

I need to negate the following sentence: "If for the integers $x, y, z$ we know that $x$ divides $y$ and $y$ divides $z$, then $x$ divides $z$." In this scenario, what does it mean for $x$ to ...
2
votes
2answers
64 views

How to prove that $(p-1)^2$ $\mid$ $(p-1)!$ when $p$ is a prime number and $p>5$?

I say that $p-1$ $\mid$ $(p-1)!$ then I want to prove that $p-1$ $\mid$ $(p-2)!$. I started by saying that $p-1$ is an even number so $2\mid (p-1)$ and that means that $\frac{p-1}{2}$ is an integer. ...
5
votes
4answers
2k views

Proof By Induction Divisibility Question: $12\mid 3^n + 7^{n-1} + 8$

Prove that $3^n + 7^{n-1} + 8$ is divisible by $12$ for all positive integers $n$. I have proved it is true for $n=1$ and I have done the 'assume $n=k$' step, but after getting $3^{k+1} + 7^k + 8$, I ...
0
votes
3answers
173 views

Euclidean algorithm for $\gcd(60,17)$

Hay I am going over some old exams and hit this: (a) Use the Euclidean algorithm to show that $\gcd(60; 17) = 1$. (b) Hence find integers $x, y$ satisfying $60x + 17y = 1$. (c) Find ...
3
votes
4answers
39 views

$\gcd(N, a)=\gcd(N, N-a)$ for positive integers $N$ and $a$?

If $\gcd(N, a)=1$, then we have $\gcd(N, N-a)=1$. More generally, can we have $\gcd(N, a)=\gcd(N, N-a)$ for positive integers $N$ and $a$? Thanks in advance.
3
votes
8answers
112 views

Proving that $12^n + 2(5^{n-1})$ is a multiple of 7 for $n\geq 1$ by induction

Prove by induction that $12^n + 2(5^{n-1})$ is a multiple of $7$. Here's where I am right now: Assume $n= k $ is correct: $$12^k+2(5^{k-1}) = 7k.$$ Let $n= k+1 $: $$12^{k+1} + 2(5^k)$$ ...
6
votes
7answers
137 views

How to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction?

I want to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction. My first step is replace $n$ with $1$. $2^{1+2}+3^{2(1)+1}$ $2^3+3^3$ $8+27$ $35 = 7\times 5$ The next step is assume ...
3
votes
4answers
78 views

Proving that $6^{2n+1} + 1$ is divisible by $7$ for $n\geq 1$ by induction

How should I go about solving a problem like this using induction? Would I: First test $(n = 1)$ so that $6^{2(1)+1} + 1 = 6^3 + 1 = 217/7 = 31$. Then assume $(n = k)$ so that you have $6^{2(k) + 1} ...
3
votes
4answers
74 views

Number of fingers of a Martian

I have a question about what seems to be modular arithmetic, but I can't quite get the answer. The problem goes along the lines of: It is often said Earthlings use the decimal system because they ...
1
vote
0answers
52 views

Sum of $m\leq 300$ such that if $2013m$ divides $n^{n}-1$, then $2013m$ also divides $n-1$

Find the sum of all the integers $m$ with $1≤m≤300$ such that for any integer $n$ with $n≥2$, if $2013m$ divides $n^{n}-1$, then $2013m$ also divides $n-1$. Unfortunately I cannot think of ...
4
votes
0answers
60 views

$d$ and $d+1$ both dividing certain integers

\begin{align} & 1\cdot 72 \\ & 2\cdot 36 \\ & 3\cdot 24 \\ & 4\cdot 18 \\ & 6\cdot 12 \\ & 8\cdot 9 \end{align} When the divisors of a number are listed in this way, let us ...
1
vote
0answers
20 views

Bezout Coefficient for polynomials in sage?

I want to find the bezout coefficient for those 2 polynomials : $f = 1+x-x^2-x^4+x^5$ and $g = -1+x^2+x^3-x^6$ when I use the gcd function in sage the output is : ...
0
votes
1answer
39 views

Are Zero Degree polynomials Considered monics?

DO zero degree polynomials that is constant polynomials considered monic polynomials? Example F(x)=16 Does it Matter the Field or the Integral region where i take the coeficients from?Sorry if the ...
6
votes
2answers
123 views

Prove or disprove : $a^3\mid b^2 \Rightarrow a\mid b$

I think it's true, because I can't see counterexamples. Here's a proof that I am not sure of: Let $p_1,p_2,\ldots, p_n$ be the prime factors of $a$ or $b$ \begin{eqnarray} a&=& ...
45
votes
4answers
7k views

Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$

For all $a, m, n \in \mathbb{Z}^+$, $$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$
10
votes
2answers
2k views

$\gcd(b^x - 1, b^y - 1, b^ z- 1,…) = b^{\gcd(x, y, z,…)} -1$ [duplicate]

Possible Duplicate: Number theory proving question? Dear friends, Since $b$, $x$, $y$, $z$, $\ldots$ are integers greater than 1, how can we prove that $$ \gcd (b ^ x - 1, b ^ y - 1, b ^ ...
1
vote
1answer
19 views

Is it possible to compute $\sigma(AB)$ if $\gcd(A, B) = C > 1$?

Let $\sigma$ be the classical sum-of-divisors function. I know, for one, that $\sigma$ is weakly multiplicative (that is, $\sigma(xy) = \sigma(x)\sigma(y)$ whenever $\gcd(x, y) = 1$). Well, of ...
1
vote
1answer
26 views

A question about $\gcd$ and divisibility

Let $\sigma$ be the classical sum-of-divisors function. Suppose that I have the following equations: $$2n^2 - \sigma(n^2) = \frac{\sigma(n^2)}{q^k}\cdot{\sigma(q^{k-1})}$$ $$2n^2 - \sigma(n^2) = ...
3
votes
1answer
25 views

What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$?

Let $\sigma$ denote the classical sum-of-divisors function. What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$? Update: I have transferred the transcript of my attempt to an actual answer to this MSE ...
0
votes
2answers
45 views

Is there a solution to this system of equations?

Is there an integer solution to this system of equations? $$\gcd(x, \sigma(x)) = 2x - \sigma(x) = \frac{x}{3} = \frac{\sigma(x)}{5}$$
0
votes
2answers
43 views

Prove: $\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$ [duplicate]

I'm trying to prove the following statement: $$\forall_{a,b\in\Bbb{N^{+}}}\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$$ As for now I managed to prove that $n^{\gcd(a,b)}-1$ divdes $n^a-1$ and $n^b-1$: Without ...
6
votes
4answers
91 views

Divisibility of polynomials in a subfield of a field.

I am trying to prove the following assertion: Let $K\subset L$ be fields, let $f,g\in K[x]$ be such that $f\mid g $ in $L[x]$, then $f\mid g$ in $K[x]$. We clearly have that $fh=g$ for some ...
1
vote
3answers
190 views

Why does Wolfram Alpha say that $n/0$ is complex infinity?

I typed a number divided by 0 on Wolfram Alpha and thought that it would say "undefined". However, when I pressed enter it told me that the answer is complex infinity. I have always been taught ...
0
votes
0answers
27 views

When is ${(1-t^2)^{-N/2}}{\det(f_t(A))}$ expressible as polynomial?

Given a matrix valued function $f_t:\mathbb R^{N\times N} \mapsto \mathbb R^{N\times N}$. For $f_t(A)=B$ both $A$ and $B$ are symmetric. Which properties can be assigned to $f_t$, when the following ...
1
vote
2answers
35 views

Proving that $p^{\alpha + \beta + 1} \mid {n \choose k} p^{k\alpha}$ when $p^\beta \mid n$.

Let $n,\alpha\in\mathbb{N},\beta\in\mathbb{N}_0$, and let $p$ be odd prime number s.t. $p^\beta|n$. How do we prove that $p^{\alpha+\beta+1}|{n\choose k}p^{k\alpha}$ for every ...
2
votes
2answers
45 views

Prove that $12 \mid m \iff$ both $6 \mid m$ and $4 \mid m$.

Give a formal proof to the following theorem which I do not know where to start. Theorem: For all natural numbers 'm', 12 divides m only if 6 divides m and 4 divides m.
1
vote
7answers
48 views

Direct Proof on Divisibilty

Using Induction proof makes sense to me and know how to do, but I am having a problem in using a direct proof for practice problem that was given to us. The problem is: For all natural numbers $n$, ...
1
vote
2answers
53 views

prove $(m) \subset (n)$ iif $n$ divides $m$

For non-zero integers $m$ and $n$, prove $(m) \subset (n)$ iif $n$ divides $m$, where $(n)$ is the principal ideal. My attempt is following. For non-zero integers $m$ and $n$, assume that $(m) ...
-2
votes
3answers
35 views

Prove/ Disprove; if a is divisible by bc, then a is not divisible by b and a is not divisible by c [closed]

The way I am currently trying is using the contrapositive, so $a\mid b$ or $a\mid c$ $\implies$ $a\nmid bc$ so I am not sure how to prove this
1
vote
4answers
83 views

If the sum of two squares is divisible by $7$, both numbers are divisible by $7$ [closed]

How do I prove that if $7\mid a^2+b^2$, then $7\mid a$ and $7\mid b$? I am not allowed to use modular arithmetic. Assuming $7$ divides $a^2+b^2$, how do I prove that the sum of the squares of ...
3
votes
2answers
246 views

Fastest way to find if a given number is prime

Given a random number, what would be the quickest possible way of finding out whether it was prime? Obviously, one could just iterate through the number in order to see if it was divisible by ...
0
votes
1answer
71 views

Division rules for other number systems?

How could we make the same division rules for other number systems, like in our decimal system: a number is divisible with 2 if it's last digit is 0,2,4,6,8, by 3 if the sum of digits is divisible ...
9
votes
2answers
3k views

Divisibility Rules for Bases other than $10$

I still remember the feeling, when I learned that a number is divisible by $3$, if the digit sum is divisible by $3$. The general way to get these rules for the regular decimal system is ...
2
votes
1answer
38 views

Divisibility by 9 with negative number

I know the rule to check divisibility by 9: check if the sum of the digits of the number is divisible by 9. But what if the number is negative? Thanks in advance!
4
votes
1answer
27 views

$x-1$ in base $x$ counting systems

Please excuse the lack of expertise. I'm not a mathematician, nor have I studied it since high school. I was thinking about how all the digits of multiples of $9$ summed equal a multiple of $9$. I ...
5
votes
8answers
157 views

Prove with induction that $11$ divides $10^{2n}-1$ for all natural numbers.

$$10^{2(k+1)}-1 = 10^{2k+2}-1=10^{2k}\cdot10^{2}-1$$ I feel like there's something in that last part that should make it work, but I can't grasp it. Am I missing something obvious? Am I going in the ...
3
votes
1answer
71 views

Solving a Diophantine equation3

The Diophantine equation that I have to solve is: $$343x^2-27y^2=1$$ This question has already been posted by other user but it has not received an answer. I proved to solve it. This is my attempt: ...
6
votes
2answers
72 views

Show that $\gcd(a^2, b^2) = \gcd(a,b)^2$

Show that $\gcd(a^2, b^2) = \gcd(a,b)^2$. This is what I have done so far: Let $d = \gcd(a,b)$. Then $d=ax+by$ for some $x,y$. Then $d^2 =(ax+by)^2 = a^2x^2 + 2axby+b^2y^2$. I am trying to create a ...
2
votes
1answer
54 views

For what values of $n$ , does $7 \mid 5^n+1$

$7 \mid 5^n+1$ implies $5^n+1=7a$ for some integer $a$ i.e $5^n=7a-1$ Now , $5^n$ is an integer which always ends with $5$ [for any integer $n$]. Thus , $7a-1$ must also end with $5$.But , this is ...
1
vote
3answers
52 views

How to find the remainder of polynomial division?

Im trying to solve this problem but I do not understand what the question is asking: Let $n\ge 2$ be an integer and $ p_n(x) $ be the polynomial: $$ p_n(x) = (x-1)+(x-2)+\cdots+(x-n) $$ What is the ...
0
votes
1answer
20 views

Mysterious divisibility condition showing up in computation of determinant of certain sparse matrices

Notation: by the $d$'th diagonal of an $n \times n$ matrix $A$ I will denote the diagonal parallel to the main diagonal that starts in row 1, column $d$. I will extend this definition in the obvious ...
1
vote
3answers
49 views

Divisibility number theory problem

How many $k,m$ exist such that $ \frac {k^2+m^2}{2(k-m)}$ is also an integer. $k,m \in \mathbb {Z} ^ + $ My guess that there is finitely many solutions but I can't seem to be able to prove so.
5
votes
5answers
81 views

What is the biggest $n$ in $4^n$ that divides $7^{2048} - 1$?

A few days ago I stumbled on the following question, it was used in the Museum of mathematics masters tournament: What is the biggest integer $n$ in $4^n$, that divides $7^{2048} - 1$? a) 1 b) 3 ...
22
votes
7answers
4k views

Why $a^n - b^n$ is divisible by $a-b$?

I did some mathematical induction problems on divisibility $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5. Can these be generalized as $a^n$ ...
2
votes
2answers
613 views

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$ I think I got it, but is this proof correct? We can write any integer x in the form: $x = 6k, x = 6k + 1, x = 6k + 2, x = 6k + 3, x = 6k + ...
-1
votes
1answer
39 views

Let p and q be two different prime numbers [closed]

a) Let p and q be two different prime numbers. If $p+q^2│p^2+q$, prove that $p+q^2│pq-1$ b) Find all prime numbers p such that $p+121│p^2+11$
1
vote
0answers
41 views

Multiple of power of 5 with only the digits 2,5,6

after helping a friend solve a homework, I asked myself the following question: $H\subseteq\{1,2,\ldots,9\}$, $T(H)=\{n\in\mathbb{N}:$ all the digits in the decimal representation in $n$ belong to ...
1
vote
1answer
13 views

quadratic form polynomial divisibility vs. matrix pointwise multiplication.

Given matrix $V',W',Y'$ is of $d\times m (d\le m)$ ; column vector $c$ is of size $m$; $r_i, i=1,...,d$ are distinct; and each row of the matrix A is $A_i=(r_i^0 ... r_i^{d-1})$. So, A is of $d\times ...
1
vote
1answer
21 views

Given $2^n$, what is the largest power of $2$ that will divide any random concatenation of base $10$ digits of powers of $2$ ending with $2^n$?

My first thought was that it would be $2^n$ itself, for example, if you concatenate $4$ and $2$ to get $42$, that's divisible by $2$ but not by $4$. But whit $2^9 = 512$, you can concatenate $16$ and ...