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
vote
7answers
53 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
55 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) ...
3
votes
2answers
341 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
122 views

Division rules for other number systems? [duplicate]

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
67 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
33 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
160 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
84 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
75 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
56 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
61 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
22 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
64 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
89 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$ ...
-1
votes
1answer
43 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
47 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
14 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
22 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
2answers
50 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
4answers
71 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 ...
4
votes
2answers
78 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 ...
1
vote
1answer
71 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 ...
4
votes
3answers
442 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 ...
1
vote
2answers
29 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
4answers
211 views

Odd divisibility induction proof

Prove that for odd $n>3$ $$64\ | \ n^4-18n^2+17$$ I checked that for $n=5$ it works. I think I need to assume that for $2n+1$ it holds and show that $2n+3$ also holds. Any ideas?
2
votes
1answer
29 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 ...
3
votes
2answers
52 views

Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$

I have this review question for an exam and I was hoping someone can help me solve it: Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$ this is what I have so far, not sure if it is ...
1
vote
4answers
73 views

Let $a,b$ be relative integers such that $2a+3b$ is divisible by $11$. Prove that $a^2-5b^2$ is also divisible by $11$.

The divisibility for $11$ of $a^2 - 5b^2$ can be easily verified; in fact: $$a \equiv \frac {-3}{2}b \pmod {11}$$ therefore $$\frac {9}{4}\cdot b^2 - 5b^2 = 11(-\frac{b^2}{4}) \equiv 0 \pmod {11}.$$ ...
1
vote
9answers
80 views

Find integers $m$ and $n$ such that $14m+13n=7$.

The Problem: Find integers $m$ and $n$ such that $14m+13n=7$. Where I Am: I understand how to do this problem when the number on the RHS is $1$, and I understand how to get solutions for $m$ and ...
1
vote
1answer
85 views

Fermat's Little Theorem and prime divisors

Let $a,b\in\Bbb N$ and $a+b$ be an even number. Assume $a^2 - b^2 - a$ is an exact square, say $c^2$. Let $m = \frac {a+b}2$ and $n = \frac {a-b}2$. Then, $$(4m-1)(4n-1) = 4(4mn-m-n) + 1 = ...
8
votes
0answers
95 views

Remainder of dividing $3^n$ by $2^n$.

I'd like to find the remainder of dividing $3^n$ by $2^n$, that is, I'd like to find value of $r$ in the expression $$3^n=q2^n+r,$$ where $q\in\mathbb{Z}$ and $0<r<2^n$. I know that it can be ...
0
votes
3answers
32 views

Prove that if $ r,p \in \Bbb{N} $, then $ \gcd(r,rp) = r $.

Problem. Prove that if $ r,p \in \Bbb{N} $, then $ \gcd(r,rp) = r $. I tried solving this. If $ \gcd(r,p) = 1 $, then $ \gcd(r,rp) = 1 \times r $. Is that right?
1
vote
4answers
71 views

Why the $GCD$ of any two consecutive fibonnaci numbers is $1$?

Note: I've noticed that this answer was given in another question, but I merely want to know if the way I'm using could also give me a proof. I did the following: $$F_n=F_{n-1}+F_{n-2} \\ ...
5
votes
4answers
3k views

How to prove gcd of consecutive Fibonacci numbers is 1? [duplicate]

Possible Duplicate: Prove that two any consecutive terms of Fibonacci sequence are relatively prime How to prove it ? Can you help me ? Let $f_n$ be Fibonacci Sequence. ...
2
votes
5answers
121 views

Prove the existence or the non-existence of a couple of numbers ($n$,$m$) such that $n^2=m!$ [duplicate]

In recent days, while I was doing exercises on combinatorics, I thought if a number $m!$ could be a perfect square. I proved to demonstrate it through the prime factorization. My attempt: ...
1
vote
4answers
31 views

A={n∈ℤ: 6∣n and 8∣n} and B={n∈ℤ: 48∣n}. Is A⊆B?

A={n∈ℤ: 6∣n and 8∣n} and B={n∈ℤ: 48∣n}. Is A⊆B? Is B⊆A? I'm pretty sure that they are subsets of each other, because any n that 6 and 8 would both divide would have to be divisible by 6*8, but I'm ...
3
votes
3answers
51 views

Prove the sum of any $n$ consecutive numbers is divisible by $n$ (when $n$ is odd).

Let $n \in \mathbb N$ be odd. Prove that the sum of any $n$ consecutive numbers is divisible by $n$. I started out with $s = x + (x + 1) + (x + 2) + … + (x + n) = kx + n.$ What I am interested in ...
-1
votes
3answers
56 views

show that $3^{(p-1)/2} +1$ is divisible by $p$ [closed]

let $n$ be an integer $>1$, and suppose that $p=2^n+1$ is a prime. Show that $3^{(p-1)/2} +1$ is divisible by $p$ (First show that $n$ must be even)
0
votes
2answers
52 views

If $a=b+c$ then $(a,b)=(a,c)=(b,c)$

If $a=b+c$ then $(a,b)=(a,c)=(b,c)$ I was thinking of writing the Euclidean algorithm \begin{align*}a &= b\cdot 1+c\\ b &= c\cdot (-1) + (b+c)\\ c &= a \cdot 1 + ...
2
votes
1answer
55 views

How to show that $\mathbb Z+x \mathbb Q[x]$ is a GCD domain?

How to show that $\mathbb Z+x \mathbb Q[x]$ is a Bezout domain, that is, the sum of two principal ideals is again a principal ideal ? Or at least, how to show that it is a GCD domain ? (This will then ...
1
vote
1answer
59 views

Looking for an example of a GCD domain which is not a UFD

I know that every UFD (unique factorization domain) is a GCD domain i.e. g.c.d. of any two elements, not both zero, exists in the domain. I am looking for an example of a GCD domain which is not ...
2
votes
1answer
21 views

Show that there exist $k$ and $r$ such that the given sum is divisible by $n$

Let $a_{1},\dots,a_{n}$ be integers. Show that there exist integers $k$ and $r$ such that the sum $$a_{k}+a_{k+1}+\dots+a_{k+r}$$ is divisible by $n$. I am unable to find the necessary way to solve ...
0
votes
2answers
45 views

Writing a GCD of three numbers as a linear combination

i know how to find the $\gcd(5,11,2^{2015}-1)$. but i can't seem to find the linear combination. do you find it the same way we find the linear combination of two integers.
1
vote
1answer
21 views

Find GCD in Q[√3] assuming it is defined

How do I find the GCD of 24 and 49 in the integers of Q[√3], assuming that the GCD is defined?
3
votes
1answer
64 views

Find all $c\in\mathbb Z^+$ for which $\exists a,b\in\mathbb Z^+, a\neq b$ with $a+c\mid ab$ and $b+c\mid ab$

Find all $c\in\mathbb Z^+$ for which $\exists a,b\in\mathbb Z^+, a\neq b$ with $\begin{cases}a+c\mid ab\\b+c\mid ab\end{cases}$ For those $c$, prove only finitely many $(a,b)$ exist. ...
10
votes
3answers
1k views

For any $n$, is there a prime factor of $2^n-1$ which is not a factor of $2^m-1$ for $m < n$?

Is it guaranteed that there will be some $p$ such that $p\mid2^n-1$ but $p\nmid 2^m-1$ for any $m<n$? In other words, does each $2^x-1$ introduce a new prime factor?
4
votes
1answer
37 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 ...