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)

1
vote
2answers
2k views

How many positive integers less than 1000 are divisible [closed]

How many positive integers less than 1000 c) are divisible by both 7 and 11? d) are divisible by either 7 or 11? e) are divisible by exactly one of 7 and 11?
0
votes
1answer
44 views

Is there a logic for recursion rules of divisibility?

I knew the divisibility rule for 7, but my sir told me that these methods are known as recursion rules for divisibility. My sir also told them for 11, 13,17,19. But is there any logic behind it? Or is ...
0
votes
3answers
65 views

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

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$. Also... $a,b$ and $n$ are natural numbers. I feel I should begin with EEA to multiply out the gcd's, but I don't know where to go from ...
1
vote
5answers
138 views

How to show $(mn)!$ divides $(m!)^n$?

How to show $(mn)!$ divides $(m!)^n$, $m$ and $n$ is integers?
1
vote
3answers
301 views

Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$.

Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$. I thought I would do the following ... As $n$ is not divisible by $2$ and $3$ then ...
-2
votes
2answers
57 views

How many seven digit numbers are there that are divisible by eleven?

How many seven-digit numbers are there that are divisible by 11? In other words, I want to find the number of seven digit numbers that are divisible by 11.
1
vote
2answers
64 views

Show that the matrix is invertible

let $A \in M_n(F)$ be a n by n matrix with values from an unknown field $F$. $P_A(t)$ is the characteristic polynomial of $A$, and $g(t) \in F[t]$ a polynomial of an unknown degree. assume that ...
2
votes
1answer
301 views

Prove by induction that $a-b|a^n-b^n$ [duplicate]

Given $a,b,n \in \mathbb N$, prove that $a-b|a^n-b^n$. I think about induction. The assertion is obviously true for $n=1$. If I assume that assertive is true for a given $k \in \mathbb N$, i.e.: ...
0
votes
1answer
57 views

Is it true that $6|p^2 \implies 6|p$, where $p \in \mathbb{N}$

Is it true that $6|p^2 \implies 6|p$, where $p \in \mathbb{N}$ Where $6|p$ is read as 6 divides p. I've tried finding a counter example, but I can't find one.
0
votes
3answers
279 views

Prove $x^n-1$ is divisible by $x-1$ by induction

Prove that for all natural number $x$ and $n$, $x^n - 1$ is divisible by $x-1$. So here's my thoughts: it is true for $n=1$, then I want to prove that it is also true for $n-1$ then I use long ...
2
votes
6answers
66 views

Is the following True of False?

Provide a proof if true or a counterexample if false: Let a,b be two integers (not both zero), then the gcd(a,b) divides ay+bx for all for x,y ∈ Z. I tried with several cases such as gcd(5,10) = 5 ...
9
votes
3answers
231 views

Show that $(n!)^{(n-1)!}$ divides $(n!)!$

Show that $(n!)^{(n-1)!}$ divides $(n!)!$ I found this question in a text he was reading about BREAKDOWN OF PRIME FACTORS IN FACT, I decided many years, have posted some here to help, but this ...
1
vote
1answer
30 views

Computations question

a) Determine the prime factorizations of 3850 and 4125 b) Find the value of d = gcd(3850,4125) c) List all the positive divisors of d This is what I have so far. a) 3850: 11, 5, 5, 7, 2 4125: ...
1
vote
2answers
30 views

Why does p|4q also mean p|q if p is odd?

Why does p|4q also mean p|q if p is odd? It might be a simple question but it's in the answers and I want to know.
0
votes
1answer
657 views

Suppose a, b and n are positive integers. Prove that (a^n) | (b^n) if and only if a | b. [duplicate]

Suppose $a, b$ and $n$ are positive integers. Prove that $a^n\mid b^n$ if and only if $a \mid b$. I have: $$a^n\mid b^n$$ $$\implies b^n = a^n \cdot k$$ $$\implies \sqrt[n]{b^n}=\sqrt[n]{a^n}\cdot ...
1
vote
1answer
23 views

Given a, b are integers. Show that GCD(a,b) = GCD(b,a).

Where do I start? I don't really understand what the difference is between the two. It seems so logic to me that I don't know how wich parts I should explain. How to start, What is there to be ...
1
vote
3answers
56 views

If $d$ is a common divisor of $m$ and $n$, then so it is of $n$ and $m-n$

I am having trouble proving the following statement: Prove that for all integers $m$ and $n$, if $d$ is a common divisor of $m$ and $n$ (but $d$ is not necessarily the GCD) then $d$ is a common ...
3
votes
2answers
119 views

Defining the Greatest Common Divisor using Symbolic Notation

I am trying to write the definition of greatest common divisor using symbolic notation. Here is my current attempt: $d = gcd(m,n) \Leftrightarrow d \in Z \wedge max(d | m \wedge d | n)$ Any help or ...
2
votes
3answers
88 views

For every integer $n$, the remainder when $n^4$ is divided by $8$ is either $0$ or $1$.

I am trying to prove the following statement: For every integer $n$, the remainder when $n^4$ is divided by $8$ is either $0$ or $1$. So far I have figured out that $n^4 = 8m$ or $n^4 = 8m + ...
21
votes
10answers
1k views

Prove if $56x = 65y$ then $x + y$ is divisible by $11$

If $x$ and $y$ are natural numbers, and $56x = 65y$, prove that $x + y$ is divisible by $11$. I tried taking the $\gcd(56x,65y)$ using the Euclidean algorithm, but I got nowhere with it and do not ...
2
votes
2answers
76 views

Does $\pi \ | \ 2 \pi$

Does $\pi$ divide $2 \pi?$ Clearly $\frac{2 \pi}{\pi}=2$ and 2 is an integer, so it would seem to make sense to say that $\pi \ | \ 2 \pi$. Does it make sense to write, for example, $$\pi \ | \ x ...
0
votes
4answers
135 views

Prove that $53^{53}-33^3$ is divisible by $10$

Prove that $53^{53}-33^3$ is divisible by $10$ I don't know modular arithmetic, so I tried things like that: $53^3 \cdot 53^{50}-33^3=(33+20)^3 \cdot 53^{50}-33^3=(33+20)(33+20)(33+20)\cdot ...
4
votes
1answer
69 views

Methods for finding a relatively prime integer

Here's the problem: Given a prime $p$ and an integer $x$, find an integer $c$ such that $gcd(x+c,p\#)=1$ where $p\#$ is the primorial for $p$. It is straight forward to solve this problem using ...
7
votes
2answers
115 views

Does the $\gcd(2n-1,2n+1)=1?$

I am posting this to ask if my proof is correct as I haven't taken number theory in a year and I feel a bit rusty. If it isn't correct, please tell me where I went wrong so I can fix it. I want to ...
3
votes
7answers
785 views

If $\gcd(a, b) = 1$ then $\gcd(ab, a+b) = 1$?

In a mathematical demonstration, i saw: If $\gcd(a, b) = 1$ Then $\gcd(ab, a+b) = 1$ I could not found a counter example, but i could not found a way to prove it too either. Could you help me on ...
1
vote
2answers
72 views

Prove that $n^n$ is not divisible by $n!$

How can I prove that $n^n$ is not divisible by $n!$ for $n \geq 3$.
1
vote
1answer
39 views

polynomial division, gcd, question

We are asked to show that there are polynomials $p,q \in Q[t]$ such that: $p(t)*(t^4+2t^2+1)+q(t)*(t^4-3t^2-4) = t^2+1$ Is the answer the same for $t+5$ instead of $t^2+1$? What I tried doing: I ...
3
votes
3answers
529 views

How to divide by 12 quickly?

Let $n\in\mathbb N$ be divisible by 12 and $n/12<100$. Is there a way of computing $n/12$ rather quickly using mental arithmetic (e.g. for 972/12, 1044/12, etc.)? For example, the number 11 seems ...
3
votes
1answer
106 views

Divisibility by 37 proof

$\overline {abc}$ is divisible by $37$. Prove that $\overline {bca}$ and $\overline {cab}$ are also divisible by $37$. $$\overline {abc} = 100a + 10b + c$$ $$\overline {bca} = 100b + 10c + a$$ ...
0
votes
1answer
35 views

Factorization of GCD

I'm working on a question about factorization of a GCD. Let x = p$^{n1}_1$ ... p$^{nk}_k$ Is it correct to answer this with: p$^{n1}_1$ + $^{m1}_1$ ... p$^{nk}_k$ + $^{mk}_k$ ?
1
vote
2answers
65 views

Number theory proof with modular arithematic [closed]

What is the proof for: If p is an odd prime, show that $$1^n+2^n+3^n+...+(p-1)^n \equiv 0 (\mod p)$$ if $p-1$ does not divide $n$ or $\equiv -1 (\mod p)$ if $p-1$ divides $n$.
1
vote
4answers
41 views

How to prove that for all positive integers $a,b$, if $a|b$ , then $\gcd(a,b) = a$?

I don't believe there are any counter examples that can be used for this (I think it is true). Could someone help me prove it? I understand why it's true (if I was right about that), but the proof ...
1
vote
1answer
23 views

finding unknowns and proof

The procedures for using cutting-adding method for testing a number M to be a multiple of 59 are as follows: 1 cut the units digit of M 2 add the remaining integer by r times of the deleted digit. 3 ...
1
vote
4answers
67 views

Prove that if $3|(a^2+b^2)$, then $3|a$ and $3|b$, where $a, b$ are integers [duplicate]

I would like to know how to prove the above statement by contradition. Somebody said that one should prove it by this method but I have no idea what it is.
0
votes
2answers
37 views

Can you simplify a expression with an exponent that is divided by a number?

As the title suggests, I have $\;a^{(b/c)}.$ Is there any way to simplify this so that there is no dividing in the exponent?
0
votes
1answer
63 views

What is the concept behind divisibility of large numbers that contain only the digit 1?

An example question I found in a text book is : The 300 digit number with all digits equal to 1 is : A) Divisible by neither 37 nor 101 B) divisible by 37 but not by 101 C) divisible by 101 but not ...
1
vote
3answers
44 views

Reducing a fraction, divisibility and indeterminate symbol

Quick question about validity, just to make sure. When I have a fraction in a form: $$\frac{3a + 3b}{a+b}$$ and I extract the common factor 3 out to get: $$\frac{3(a+b)}{a+b} \;=\; 3\frac{a+b}{a+b}$$ ...
2
votes
2answers
143 views

7 digit number consisting of 7s and 5s

Find all the 7 digit numbers that have only 5 and 7 as their digits and divisible by both 5 and 7. I have no clue how to use divisibility of 7 to solve this problem. DO i need to check all the 64 ...
0
votes
1answer
39 views

Greatest common denominator

My problem is figuring out how to express the GCD as a linear combination of $(9,11)$. So far, I have: $$11 = 9 + 2$$ $$9 = 4 \cdot 2 + 1$$ From here, I'm not sure if I put $2 = 2 \cdot 1$ As for ...
3
votes
3answers
122 views

How prove this $\binom{n}{m}\equiv 0\pmod p$

let $p$ is prime number,and such $p\mid n,p\nmid m,n\ge m$ show that $$p\>\Big|\>\binom{n}{m}$$ I know that: if $p$ is prime number,then $$\binom{n}{p}\equiv \left[\dfrac{n}{p}\right] \pmod ...
2
votes
2answers
141 views

Prove that every odd natural number divides some number of the form $2^n - 1$ [duplicate]

Suppose that $m$ is an odd natural number. Prove that there is a natural number $n$ such that $m$ divides $2^n -1$. I have absolutely no idea how to tackle this; any assistance would be welcome.
0
votes
1answer
35 views

Number theory problem divides

In class today we were talking about proving the definition of 'divides' and the teacher never got to finish this proof. if a divides b^2 , then a divides b. First line was: Let a and b be ...
2
votes
3answers
87 views

Prove that if $a|b$ and $a|c$, then $a\mid(c-b)$.

I'm having trouble proving this one. I know its true. Any ideas? Here is what I have so far: If $a\mid b$, then there exists an integer $q_1$ such that $b = aq_1$. If $a\mid c$, then there exists an ...
7
votes
8answers
268 views

Why is $2x^3 + x$, where $x \in \mathbb{N}$, always divisible by 3?

So, do you guys have any ideas? Sorry if this might seem like dumb question, but I have asked everyone I know and we haven't got a clue.
5
votes
2answers
77 views

GCD and the Riemann zeta funtion

I'm completely stuck on this one, as I'm just starting with analytic number theory: How to write $$\sum_{a\in\mathbb{N}}\sum_{b\in\mathbb{N}}\frac{(a,b)}{a^sb^t}$$ in terms of the Riemann zeta ...
8
votes
3answers
691 views

Prove that $x$ and $x+1$ are coprime numbers

Given $\{x \mid x > 1\}$, how do I prove that any given $x$ and $x+1$ are coprime?
0
votes
2answers
41 views

Concatenation of strings

We have two strings A and B. We have to find if for some n,m A concatenated n times equals B concatenated m times or not. I have made an interesting observation but am unable to prove it.It appears ...
1
vote
0answers
89 views

When is a number like “ddd…ddd”+1 (where d is a digit) a perfect square or a prime?

Inspired by Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?, I wonder when numbers like these are perfect squares. Certainly, all numbers of the form $000...0001$ are ...
18
votes
4answers
1k views

Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?

I know that if the number is a perfect square then it will be congruent to 0 or 1 (mod 4). Now since the number is even, I know that it is either 0 or 2 (mod 4). How would I go about answering this? ...
0
votes
2answers
91 views

How to show the existence of a number with certain divisibility conditions between two multiples?

How can we show that between two even natural numbers they're exists a natural number that isn't even? How can we show that they're exists a natural number that is odd and not divisible by 3, between ...