This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms

0
votes
2answers
43 views

Induction proof, divisibility

I'm struggling with an induction problem here. I have to prove that $2^{2^n}- 6$ (two to the power of two to the power of $n$ minus six) is divisible by $10$. I already figured some steps and I ...
1
vote
3answers
251 views

Greatest common Divisor of negative numbers

To find gcd of negative numbers we can convert it to positive number and then find out the gcd. Will it make any difference?
2
votes
1answer
77 views

Find all positive integers solutions such that $3^k$ divides $2^n-1$

How can I find all positive of $k$ and $n$ such that $$\frac {2^n-1}{3^k}$$ is an integer? I know that $$2^n-1\equiv 0\pmod 3$$ If $n=2p$ with $p$ integer , $$2^n-1\equiv 0\pmod 9$$ If $n=6p$, ...
0
votes
2answers
479 views

Find the $\gcd(81,237)$ and express it as a linear combination of $81$ and $237.$

How are they finding the encircled part. I am trying my very best to understand it, but in vain.
0
votes
3answers
46 views

Find all $\displaystyle n \in \mathbb{Z}$ such that $\displaystyle k = \frac{1+4n}{5}, \qquad (k \in \mathbb{Z} )$

My question is rather general but I got stuck in that issue after trying to solve a trigonometric equation. After simplifying I got this: $$\sin \left(\frac{5x}{4}\right) + \cos x = 2$$ which is ...
-3
votes
1answer
103 views

Prove that there exist $2015$ consecutive abundant numbers [closed]

A positive integer $N$ is called abundant if the sum of its divisors is greater than $N$: $\delta (N) >N$. My question is: Prove that there exists an integer: $k\in\mathbb N\setminus\{0\}$ ...
3
votes
4answers
59 views

Prove that if $p$ is prime greater than $3$ ,then: $p^2+2015$ is multiple of $24$?

Prove that if $ p $ is prime number $(p >3)$, then the number $p^2+2015$ is multiple of $24 $? Thank you for any help
2
votes
1answer
77 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
3k 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 ...
3
votes
4answers
55 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.
1
vote
1answer
61 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 ...
1
vote
0answers
71 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 : ...
4
votes
4answers
115 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} ...
0
votes
1answer
72 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 ...
1
vote
1answer
34 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 ...
4
votes
0answers
75 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
1answer
34 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
42 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
1answer
174 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 ...
1
vote
3answers
561 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
2answers
59 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}$$
4
votes
0answers
91 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 ...
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
123 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
75 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
1answer
194 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!
5
votes
1answer
38 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
3answers
119 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 ...
3
votes
1answer
88 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
6answers
169 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 ...
1
vote
3answers
68 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 ...
2
votes
4answers
123 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 ...
2
votes
2answers
65 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
71 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
104 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 ...
1
vote
1answer
36 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 ...
4
votes
2answers
67 views

Divisibility of numbers

Find all positive integers $x,y$ such that $2x+7y$ divides $7x+2y$. I somehow managed to show that $x$ is greater than $y$. But couldn't proceed further.
1
vote
0answers
63 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
26 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 ...
3
votes
4answers
183 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 ...
6
votes
1answer
108 views

Proof that $\gcd(2^m-1,2^n+1)=1$ for odd $m$ using group theory

Below is a perfectly fine proof using basic tools of number theory: Showing $\gcd(2^m-1,2^n+1)=1$ Could we prove this more quickly using group theory? I would be very interested in seeing an ...
3
votes
2answers
56 views

How to prove that if $m$ is squarefree, then $d^2 \lvert mb^2 \implies d \lvert b$

This statement was given in my number theory textbook when analyzing quadratic fields, and I am not seeing how to prove it. $m$ is a squarefree (not divisible by the square of any number) integer and ...
1
vote
3answers
89 views

Dividing by Zero Using Exponents

I am sorry if I am missing some fundamental rule disproving my question, but I am very confused here. So $0^0 = 1$ and $x/x = x^0 = 1$ so if $x = 0$ $0/0 = 1$ The problem here is people have ...
3
votes
8answers
169 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)$$ ...
1
vote
1answer
111 views

The following is a necessary condition for a number to be prime, from its digit expansion. Has it been referred somewhere?

Concerning a numbers’ digits we know some necessary conditions on them for the number to be prime, besides the last digit having to be odd (except for prime 2). For example in decimal representation ...
1
vote
2answers
33 views

if d divides n then prove that fibonacci of d divides fibonacci of n

prove that if $d$ divides $n$ then prove that fibonacci of $d$ divides fibonacci of $n$. i have tried to write $F(n)$ as a multiple of $F(d)$ using the fact that $n = ad$ for some natural $a$ but got ...
4
votes
3answers
475 views

Prove that the integers $x$, $x+6$, $x+12$, $x+18$, $x+24$ can only be prime if $x$ is $5$.

Prove that the integers $x$, $x+6$, $x+12$, $x+18$, $x+24$ can only be prime if $x$ is $5$. I am very new to proofs and not completely sure of how to approach this one. I tried several different ...
4
votes
2answers
111 views

Find all values of $x,y,z$ positive integers such that $4^x+4^y+4^z$ is a perfect square

I have to solve the equation $$4^x+4^y+4^z=k^2$$ I posted my solution but i don't know if there are other solution. How can i demonstrate that this expression is a perfect square? Are there oter ...
2
votes
1answer
53 views

Find remainder when $20^{13}$ is divided by $4940$

Find remainder when $20^{13}$ is divided by $4940$ I have solved this, but am hoping for an elegant solution. My solution: $r(20^{13}||4940) = 20 \times r(20^{12}||247)$ where $r(a||b)$ is the ...