Tagged Questions

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

62 views

Systems of linear modular equations with unknowns in the moduli

I am interested in systems of linear modular equations, where the unknowns also appear in the moduli. The general form would be: $A \vec{x}= \vec{b} \;\textrm{mod} \; (C \vec{x}+\vec{d})$ where A ...
2k views

Prove that there exists a number divisible by 1999 with digit sum 1999

My nephew in the secondary school asked me how to solve the problem as stated in the title. Honestly, I do not have any idea how to do it: Prove that there exists a positive integer number such ...
90 views

Do odd numbers have only odd divisors?

Is it true, that odd numbers have only odd divisors? If yes, what would a formal proof look like?
59 views

For numbers divisible by three, why is the sum of their digits able to be divided by three? [duplicate]

When you add the digits of any number that is divisible by three, that sum of those digits also appears to be divisible by three (with no remainder). For example a number (which I randomly grab from ...
40 views

Prove that $\begin{pmatrix} 2n \\ n \end{pmatrix}$ is not divisible by $p$

Let $n$ be an integer greater than $5$. I would like to prove that if $p$ is a prime such that $\displaystyle \frac{2}{3}n < p \leq n$ then $\displaystyle \begin{pmatrix} 2n \\ n \end{pmatrix}$ is ...
25 views

Isolating Decimals

I'm in need of isolating the decimal part of a number using maths only, no excel functions or anything like that, but it's proving to be much harder than I thought it would be. For example, I have ...
87 views

I've seen this fact stated (or alluded to) in various places, but never proved: Let $n$ be a positive integer, let $m \in \{1,2,...,n-1\}$. Then $$\gcd(2^n-1, 2^m+1) = \begin{cases} 1 ... 3answers 18 views Remainders and modulars How do I find the remainder of 3^{2002} divided by 5 using mod? I can solve the remainder of, for example, 7^{220} divided by 8 because 7=-1 \pmod 8, but that doesn't work here. 1answer 39 views Showing existence in proof of Division Algorithm using induction Division Algorithm: Let a, b \in \mathbb{Z} be any integers and b \neq 0. Then, \exists unique integers q, r such that a = bq + r and 0 \leq r < |b|. I am trying to show ... 1answer 84 views Show that there exist infinitely many i such that a_i-1 is divisible by 2^{2015} Let (a_n) be a sequence defined by: a_o=2, a_1=4, a_2=11 and \forall n \geq 3,$$a_n = (n+6)a_{n-1}-3(2n+1)a_{n-2}+9(n-2)a_{n-3}$$Show that there exist infinitely many i such that a_i-1 is ... 3answers 61 views Euclid's proof on the infinity of primes Could someone shed some light on this? I perfectly understand Euclid's proof on the infinity of primes. Let's suppose there is a largest prime, p, and then let's make a number, n, so that n = (2 x 3 ... 2answers 49 views n>k>0 are integers , then among the integers n , n+1 , …, n+k-1 , there is an integer containing a prime divisor greater than k ? [closed] If n>k>0 are integers , then how to show that among the integers n , n+1 , ..., n+k-1 , there is an integer containing a prime divisor greater than k ? 1answer 46 views 2(n-2)+1 does not divide (n-2)(n-3)/2 for n \ge 8 For n \ge 8 the number 2(n-2)+1 never divides (n-2)(n-3)/2. Any ideas how to prove this? I see that (n-2)(n-3)/2 = 1 + 2 + \ldots + (n-3). If I suppose that 2(n-2)+1 divides ... 3answers 121 views Prove that \sqrt{3} is not a rational number [duplicate] There is a similar question however that question asks why 3 |p^2. Here the question is about  3 | p^2 \rightarrow 3 | p. It is a simple exercise (1.2.1) from Abbot's "Understanding Analysis". ... 4answers 110 views Is it correct that \frac{1}{0}=\frac{1}{-0} and if it is, why is \frac{1}{0} \neq 0? This is a genuine question, I am not trying to convince anyone. But I'm sure hundreds of people already considered this, so if you can point out where I'm wrong, it would be much appreciated. If we ... 2answers 48 views Proof for elementary divisibility problem Not sure if my thinking is correct. For the problem "a divides b if and only if a divides b^2." So far my proof goes: since a divides b there exists an integer n such that b=an. Then ... 0answers 38 views Prove that 2\mid x and 5\mid x if and only if 10\mid x I have to do it without using Fundamental Theorem of Arithmetic. Can someone check my work? Prove if 2\mid x and 5\mid x, then 10\mid x. Let x \in \mathbb{Z}. Suppose 2\mid x and 5\mid ... 6answers 249 views If  a + b + c \mid a^2 + b^2 + c^2 then  a + b + c \mid a^n + b^n + c^n for infinitely many n Let  a,b,c positive integer such that  a + b + c \mid a^2 + b^2 + c^2. Show that  a + b + c \mid a^n + b^n + c^n for infinitely many positive integer  n. (problem composed by Laurentiu ... 0answers 87 views 1+2^x+\ldots+n^x \mid 1+2^y+\ldots+n^y for all n implies x=y? The following problem was proposed by A. Schinzel a couple of days ago at the 22nd Conference on Number Theory, held in Liptovsky Jan (Slovakia). He pointed out that the question has an affirmative ... 5answers 140 views Mathematical induction: 9 divides n^3 + (n+1)^3 + (n+2)^3 [duplicate] Prove that 9 divides n^3 + (n+1)^3 + (n+2)^3 where n is a nonnegative integer. I have seen many questions on this site that contain the answer to this problem and I already know the solution, ... 3answers 79 views Using induction to prove that 2 \mid (n^2 − n) for n\geq 1 Use induction to prove that, for all n \in \mathbb{Z}^+, 2\mid (n^2 − n). That is, I am supposed to use induction to prove that (n^2 − n) can be divided by 2 when n is a positive ... 5answers 92 views How can I prove that 2^{n+2}\mid(2n+3)!? I'm not sure where to proceed or how to go about proving this assertion holds for all natural numbers n:$$2^{n+2} \mid(2n + 3)!$$The base case is n=1, where 2^{1+2}\mid(2\cdot 1+3)! which ... 4answers 43 views Show that 2|n(n+1) using induction [duplicate] Show that 2|n(n+1) using induction I tried but im stuck , it still (n+1)(n+2) Two successive numbers It's simple using the the methode that n=2k or n=2k+1 Can someone help or give a hint ? 7answers 351 views Proving by strong induction that \forall n \ge 2, \;\forall d \ge 2 : d \mid n(n+1)(n+2)…(n+d-1)  I'm trying to prove by induction the following statement without success:$$\forall n \ge 2, \;\forall d \ge 2 : d \mid n(n+1)(n+2)...(n+d-1) $$For the base case: n = 2, d = 2 2\mid 2(2+1) ... 1answer 81 views Is it possible for (900q^2+ap^2)/(3q^2+b^2p^2) to be an integer? The original problem is: "Find all possible pairs of positive integers (a, b)$$k = \dfrac{a^3+300^2}{a^2b^2+300}\tag1$$such that k is an integer." I've tried so many different ways. Now this ... 1answer 70 views Suppose a, b, and c are integers. Prove that if a \mid b and a \mid c, then a \mid (b +c) [duplicate] Suppose a, b, and c are integers. Prove that if a \mid b and a \mid c, then a \mid (b +c) 1answer 39 views Does there exist positive integers a,b,n , where n>1 , such that a^n - b^n |a^n + b^ n ? Does there exist positive integers a,b,n , where n>1 , such that a^n - b^n |a^n + b^ n ? ; the only trivial thing I can see is that if so happens , then a^n - b^n | 2b^n , but nothing else ... 2answers 30 views a,b be two positive integers , where b>2  , then is it possible that 2^b-1 \mid 2^a+1? If a,b be two positive integers , where b>2  , then is it possible that 2^b-1\mid2^a+1 ? I have figured out that if 2^b-1\mid 2^a+1, then 2^b-1\mid 2^{2a}-1 , so b\mid2a and also a ... 0answers 128 views Connections between Fibonacci and natural numbers Here are some known facts about the Fibonacci numbers and then some questions regarding them . 1.Carmichael's theorem : For every n>12 F_n has a prime divisor which doesn't divide any of ... 3answers 2k views The least perfect square, which is divisible by each of 21,36 and 66 is (options) (a) 213444 (b) 214344 (c) 214434 (d) 231444 Any short method to solve this question in 1 min? 2answers 90 views Prove p is prime Let p be an integer with this property: whenever b, c \in \mathbb Z such that p\mid bc, then p\mid b or p \mid c. Prove p is prime. Here is my attempt at a proof: Suppose d \mid p. Then ... 2answers 66 views b divides a \Leftrightarrow -b divides a Prove that b divides a if and only if -b divides a. I'm thinking something like a = bp and b = aq, then go on from there? It seems simple enough but thanks for the help in advance! 0answers 19 views If a, b, c, d \in \mathbb Z and p is a prime factor of a - b and c - d, then p is a prime factor of (a + c) - (b + d) By hypothesis, p \mid (a - b), (c - d). Then p \mid [(a - b) + (c - d)]. In other words, p \mid [(a + c) - (b + d)]. Does it work? 2answers 43 views Number of divisors d of n^2 so that d\nmid n and d>n I just wanted to share this nutshell with you guys, it is a little harder in this particular case of the problem: Find the number of divisors d of a^2=(2^{31}3^{17})^2 so that d does not ... 2answers 97 views Proof that expression is integer, \frac{(2n)!}{n!(n+1)!} can you help me with this excercises.. Proof that expression is integer,$$\frac{(2n)!}{n!(n+1)!}$$I've tried for induction!! p(1):\frac{(2)!}{2}=1  for p(k)=\frac{(2k)!}{k!(k+1)!} for ... 2answers 40 views Number 9 and age of mother when child is born. If a mother's age is divisible by 9 when a child is born then once you go to the next decade,n every 11 years the child's age and mother's age are always the same two numbers in reverse order. For ... 3answers 133 views If \gcd(ab,c)=d and c|ab then c=d For all positive integers a, b, c and d, if \gcd(ab, c) = d and c | ab, then c = d. Need help proving this question, I know that abx + cy = d for integers x,y and that c|ab can be ... 2answers 144 views Divisibility and GCD proof I'm having trouble with this simple proof. Any help would be appreciated. I don't really know where to start to try to conquer this problem. Suppose a|m, b|m and \gcd(a,b) = 1. Prove, ... 1answer 31 views If a, b \mid c \text { and } \gcd(a, b) = d, \text { then } ab \mid cd  a \mid c \to c = ak \text { and } b \mid c \to c = bj. ak + bj = 2c = d \to c \mid d. d \mid a \to a = dj. c = ak = d(jk) \to d \mid c. So, c = d. a \mid c \text { and } b \mid c ... 0answers 36 views About the least common multiple of numbers and combinatorial Prove that for any positive integer n, the least common multiple of the numbers 1, 2, 3, \ldots , n and the least common multiple of the numbers: {n\choose 1}, {n\choose 2}, \ldots , {n\choose ... 1answer 114 views Difficult sets of Equations, counting Let  m be the number of solutions in positive integers to the equation  4x+3y+2z=2009, and let  n be the number of solutions in positive integers to the equation  4x+3y+2z=2000. Find the ... 0answers 256 views Dividing the whole into a minimal amount of parts to equally distribute it between different groups. Suppose we have a finite amount of numbers x_1, x_2, ..., x_n (x_i\in\mathbb{N}) and an object that should be divided into parts in such a way that it can be without further dividing distributed ... 1answer 58 views Missing values of the ratio \frac{(x+y+z)^2}{x^2+y^2+z^2} Let x,y,z be some positive integers. Is it true that we cannot find any positive integer n for which$$ \frac{(x+y+z)^2}{x^2+y^2+z^2}=1+\frac{2}{3n}\,\,? $$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 ... 0answers 221 views A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have? A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have? options given: (a) either 1 or 2 (b)1 or 3 (c)either 2 or ... 4answers 127 views Why Zero divided by Zero is undefined and not Infinity [duplicate] apologize in advance if this is a duplicate, but I found a lot questions related to this but none answering this specific question. My logic is: let's consider division the opposite of ... 3answers 161 views when {\rm gcd} (a,b)=1, what is {\rm gcd} (a+b , a^2+b^2)? [duplicate] I want to prove above statement "what is {\rm gcd} (a+b , a^2+b^2) when {\rm gcd}(a,b) = 1" I've seen some proofs of it, but i couldn't find useful one. here is one of the proof of it. some ... 2answers 53 views How to find \frac{a+b+c}x? [closed] ab and bc are two digit numbers. if ab*x=2  and bc*x=3 then find \frac{a+b+c}x. (* is multiplication) It looks simple but I couldnt go further.$$17b=2(15a-c)\iff b\mid2 \quad and\quad ...
I am using the definition of odd and even integers along with bezout's theorem and I end up with something of the form $d=(2k)m+(2l+1)p$ where $a=2k$ and $b=2l+1$. I've tried to use contradiction as ...