Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

0
votes
2answers
359 views

When $\frac{a^2+b^2}{a-b}$ is a divisor of 2015?

Is it possibly to prove this problem? Yes! Prime factorisation of 2015 and then? Find all pairs of positive integers $(a,b)$ for which $\frac{a^2+b^2}{a-b}$ is an integer and divides 2015.
1
vote
1answer
80 views

Euclid's lemma proof

Is there a proof the uniqueness of q and r in $$a=bq+r$$ where a and b are positive integers and $$0\leq r <b$$ A claim can be made like this ... Let $$a=bq_{1}r_{1}$$ where $$0\leq r_{1}<b$$ ...
0
votes
1answer
39 views

Find smallest $n$ such that $a$ divides $b^n-1$

Suppose $a$ and $b$ are relatively prime integers $\geq 2$. I need to find the smallest positive integer $n$ such that $b^n-1$ is divisible by $a$. Is there an efficient algorithm for finding this, ...
3
votes
1answer
72 views

A combinatorial conjecture

I'm trying to prove the following conjecture. Conjecture. Let $p \equiv -1\!\pmod{6}$ be a prime, and let $a,b > p$ be integers with $p \nmid ab(a+b)$. Then $$ \sum_{r=0}^{p-3} ...
3
votes
2answers
169 views

Why are these two conversion methods (base 10 to base 2) equivalent

I've come across two methods for converting a base 10 number into its base 2 equivalent. I want to know why they are equivalent. Method 1: We're given a number $N$ to convert into binary 1) Find the ...
7
votes
4answers
132 views

Which was defined first to represent $\underbrace{a+a+a+\cdots+a+a+a}_{n \text{ terms}}$? $n\times a$ or $a \times n$?

When we are talking about multiplication, we often use it without knowing which one was defined first and which one was defined because of its commutative property. Here I want to know which one was ...
0
votes
1answer
46 views

General Rule for calculating solutions to ax+by= 1 where (a,b)=1

A friend and I are in an intro to number theory class at UK and were struggling to prove the theorem that states that for two relatively prime integers $a$ and $b$ there exist integers x and y which ...
1
vote
2answers
82 views

how to calculate the remainder when the number is divided by 1000

$n=(2^{2014}-1)/3$ what is the remainder when it is divided by $1000$. i wrote $2$ as $3-1$ and proceeded but that only helped me prove $n$ is a integer but i dont know how to find the remainder on ...
4
votes
3answers
115 views

Prove the following fraction is irreducible

Prove $\frac{21n + 4}{14n + 3}$ is irreducible for every natural number $n$. I was thinking of taking a number-theory based approach. Can you suggest the following method Calculus/Number theory ...
3
votes
1answer
46 views

Construct a function $f:\Bbb{R}\to [0,\infty)$ such that every point $x\in\Bbb{Q}$ is a local strict minimum point of $f$

I got this problem: Construct a function $f:\Bbb{R}\to [0,\infty)$ such that any point $x\in\Bbb{Q}$ is a local strict minimum point of $f$ My partial solution: Define $f$ by $f(x)=1$ if ...
-1
votes
1answer
69 views

A large number divisible by 4 [closed]

Let $S=\displaystyle x! + \sum_{k=0}^{2013} k!$, where $x$ is a one-digit non-negative integer. How many possible values of $x$ are there so that $S$ is divisible by 4?
2
votes
3answers
187 views

Sum of squares of two integers divisible by five [closed]

Supposing $x,y$ are natural numbers, what is the probability that the sum of their squares are divisible by 5? I am getting $1/3$ as squares can only end with $0,1,4,5,6,9$. So $36$ pairs are ...
0
votes
2answers
125 views

Induction and Maximum Principle

I wish to show that the following two assertions are equivalent: (Principle of Mathematical Induction) Let $S$ be a nonempty subset of the set of non-negative integers satisfying the following two ...
0
votes
3answers
46 views

How to prove $\gcd(a+m,b)=d$ when given $\gcd(a,b)=d$ and $b|m$?

some say I shall use $a+m-m$..... But I do not get it. Since $\operatorname{gcd}(a,b)=d$ then $a=q_1d$ and $b=q_2d$ And $b|m$ give $m= q_3b = q_3 q_2 d$ then $$a+m = q_1d+q_3q_2d = (q_1+q_3q_2)d$$ ...
0
votes
1answer
58 views

divisibility of integer 7 [duplicate]

For any value of $y$, is $7|y^2 + 1?$ and $3|y^2 +1$? as well as $19|y^2 +1$? If there is no such $y$, how do you prove it. Also, I want to know about free software to check these type of ...
0
votes
1answer
44 views

Divisions with prime cases of equations

For an ODD integer $x$ let us define $y^2 + 1 = (x + 2) (x^2 -2x + 4)$ is there any prime $p$ such that $p\mid(x^2 -2x + 4)$ or $p\mid(x+2)$ in order to $ p|y^2 +1$
1
vote
3answers
281 views

$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}?$ [duplicate]

How do I show that for $n \geq 0$, $$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}?$$ I know that $\sum_{k=0}^n \binom{n}{k} = 2^n$, but does this really tell me anything? Thanks.
0
votes
1answer
23 views

Binomial expression involving union and intersection of sets?

Let $\mathcal{U}$ and $\mathcal{V}$ be disjoint sets containing $m$ and $n$ elements, respectively, and let $\mathcal{F} = \mathcal{U} \cup \mathcal{V}$. Show that the number of subsets $\mathcal{A}$ ...
3
votes
2answers
189 views

Not a perfect square of the form for any integer x.

Now a days, I become good fan of this site, as this site making me to learn more math..hahaha. Okay! Can we prove that $x^3 + 7$ cannot be perfect square for any positive/negative or odd/even ...
2
votes
2answers
77 views

For which primes $p$, $p+10$ and $p+14$ are also primes?

For which primes $p$, $p+10$ and $p+14$ are also primes? I assume it has something in common with division (whether the prime $n$ is divisible by some number), but that is just the first idea that ...
4
votes
1answer
55 views

Diophantine equation $x^2+y^2+1=xyz$ [duplicate]

Let $x,y,z$ be positive integers such that $x^2+y^2+1=xyz$. Show that $z=3.$
1
vote
2answers
117 views

Natural numbers object via initial morphism

I assume that a natural number object (or see nLab) can be defined as an initial morphisms. (edit: as in the title, I ment initial morphism, not objects) $\hspace{1cm}$ Thoughts: Probably $X:=1$, ...
3
votes
2answers
146 views

Do Lipschitz/Hurwitz quaternions satisfy the Ore condition?

The Lipschitz quaternions $L$ are the quaternions with integer coefficients and the Hurwitz quaternions $H$ are the quaternions with coefficients from $\Bbb Z\cup(\Bbb Z+1/2).$ A ring satisfies the ...
2
votes
2answers
52 views

divisibility on prime and expression

This site is amazing and got good answer. This is my last one. If $4|(p-3)$ for some prime $p$, then $p|(x^2-2x+4)$. can you justify my statement? High regards to one and all.
0
votes
4answers
55 views

The divisibility of the values of quadratic polynomials in $x$, for integer $x$

I would like to know method of finding validity of the statement by proofs. 1) $8$ does not divides $x^2 - 7$ for any integral value of $x$? 2) For any odd integer $x;$ the term $(x-1)^2$ is always ...
0
votes
2answers
77 views

Find integers x and y with 103x + 113y=1

Find integers $x$ and $y$ with $103x + 113y=1$ How would you solve this problem? I'm thinking maybe you can use Euclidean Algorithm to solve for the inverse?
3
votes
1answer
137 views

how to find the last non-zero digit of $n$

I want to know how to find the last non-zero digit of $n$. For example $n = 100!$ my try: First i have to know how much Zeros $100!$ has so i did this: $$E_{5}100 = \sum _{1\leq k <n} ...
2
votes
1answer
361 views

The number $2^{29}$ has $9$ distinct digits. Find the missing digit without the use of a calculator. [duplicate]

$2^{29}$ has $9$ distinct digits. Find the missing digit without the use of a calculator. I've seen its solution before but I still don't understand it. Math novice here. A detailed answer will ...
2
votes
2answers
692 views

Prove that if a and b are positive integers, then there exists integers x and y such that 1/lcm(a,b)=x/a+y/b

My professor has not taught us the technique of writing proofs, he just continues to do them for us in class. So I am really stumped on this proof. Any help is greatly appreciated!
2
votes
5answers
2k views

Is it true that $n^2+3n+13$ is prime for all $n\in\mathbb ℤ^+$?

Prove or disprove the statement: If $n\in\mathbb ℤ^+$, then $n^2+3n+13$ is prime. I am lost here. All I know is that $n$ is greater than or equal to one, since it is a positive integer.
-1
votes
1answer
1k views

Is there any shortcut to find if a number is a perfect cube?

Is there any shortcut to find if a number is a perfect cube? I am taking for instance finding if a number is a perfect square. So , if a number ends with 2,3,7,8. It cannot be a square. But if it ...
0
votes
3answers
104 views

Proof that the greatest common divisor of $(a, a+2)$ is $2$ if $a$ is even and $1$ if $a$ is odd

Some help would be great on this, my teacher hasn't explained how to construct proofs to us, he just keeps doing them for us in class. I have at the beginning: Let a be even. Since the sum of two ...
1
vote
2answers
186 views

Which of the following are reduced modulo residue systems modulo 18?

Question: Which of the following are reduced modulo residue systems modulo 18? $a. 1,5,25,125,625,3125$ $b. 5, 11, 17, 23, 29, 35$ $c. 1, 25, 49, 121, 169, 289$ $d. 1, 5, 7, 11, 13, 17$ Attempt: ...
2
votes
1answer
38 views

Property of abelian groups without using Lagrange's theorem

I need to prove the following without using Lagrange's Theorem: Show that for an abelian group $G$, $\forall \; a \in G:$ $a^{o(G)}=e$ . This is a generalization of the Euler-Phi Theorem. So I ...
1
vote
3answers
43 views

Proving $\sum_{k=0}^n \binom{n}{k} = 2^n$ combinatorially?

I am trying to prove the basic fact that $$\sum_{k=0}^n \binom{n}{k} = 2^n$$ I can use the binomial theorem, simply setting $x = y = 1$, but how can I prove this combinatorially? Thanks.
0
votes
3answers
54 views

The only positive divisor of both $a$ and $a + 1 $ is $1$

Prove that if $a \in \mathbb Z$ then the only positive divisor of both $a$ and $a + 1$ is $1$. When I saw this statement I didn't understand it. The only way that I can see it being true is if a is a ...
4
votes
6answers
121 views

Show that $\forall n\in\Bbb{N}, (3+\sqrt 7)^n+(3-\sqrt 7)^n\in\Bbb{Z}$ and that $\forall n\in\Bbb{N}, (2+\sqrt 2)^n+(2-\sqrt 2)^n\in\Bbb{Z}$

I got this problem which I encountered during a limit of sequence calculation: Show that $\forall n\in\Bbb{N}, (3+\sqrt 7)^n+(3-\sqrt 7)^n\in\Bbb{Z}$ And that $\forall n\in\Bbb{N}, (2+\sqrt ...
1
vote
1answer
71 views

How many solutions does the equation $2i+j+3k=l$ have in nonnegative integers?

Let $i,j,k$ be nonnegative integers and $l$ be a positive integer. How many solutions does the equation $2i+j+3k=l$ have? For low enough $l$, I can easily find the number of solutions, but is there ...
1
vote
1answer
42 views

Proof that $(ab+cd)^{\frac{1}{n}}$ is irrational?

Let $a,b,c,d,n >2, \gcd(a,b,c,d)=1$, how can I prove that $\sqrt[n]{ab+cd}$ is irrational if $\sqrt[n]{a},\sqrt[n]{b},\sqrt[n]{c},\sqrt[n]{d}$ are irrational? Any hint?
0
votes
1answer
54 views

How many times must you square a number to get $<1/2$

Let $0\leq x<1$. Be given. How many times must you square $x$ to get less than $1/2$? Clearly this depends on $x$. But is there a nice formula to determine this? Such as: To make ...
1
vote
2answers
41 views

Proof of Little Fermat's Theorem for a=7

In the book I read there are proofs of FLT for certain cases before the common case. When a=7, authors first write that it's possible to check all remainders of $a\mod7$, and then that it's ...
2
votes
2answers
301 views

partitions and their generating functions and Partitions of n

A partition of an integer, n, is one way of writing n as the sum of positive integers where the order of the addends (terms being added) does not matter. p(n, k) = number of partitions of n with k ...
1
vote
2answers
66 views

How do you solve $k(a^2-b^2)=2(ax-by)$?

let $a,b,c,d,x,y,k$ be all non-zero positive integers >1. If $a^2-b^2 \neq0$,how do you find all the pairs $(x,y)$ such that $k(a^2-b^2)=2(ax-by)$. I have found so far only solutions where ...
1
vote
3answers
60 views

Simplifying a proof by contradiction: if $a\equiv 1\bmod 5$, then $a^2\equiv 1\bmod5$

Prove the following either by Direct Proof or by Contraposition: Suppose $a\in\mathbb{Z}$, if $a\equiv 1\pmod 5$, then $a^2\equiv 1\pmod5$ Suppose $a\equiv 1\pmod 5$ Then $5|\left(a-1\right)$, ...
1
vote
1answer
53 views

Hilberts Theorem (norm group)

The theorem says the following: The map $N$ is a group homomorphisim from the multiplicative group of $\mathbb{Q}^{x}[i]$ to the multiplicative group of $\mathbb{Q}^{x}$ and has kernel $\lbrace ...
0
votes
2answers
95 views

When is the product $(1+1/3)\cdots(1+1/n)$ equal to an integer?

It looks like its never the case. Is that right?
1
vote
2answers
260 views

Prove that if $\gcd(a,n)=1$, then the integers $c,c+a,c+2a,\ldots,c+(n-1)a$ form a complete set of residues modulo $n$ for any $c$

I am guessing I need to show that the given integers equal $0,1,2,\ldots, (n-1)$ mod n taken in some order. However I am not sure on how to start, Any help ?
1
vote
1answer
150 views

The digit 3 and 2 digit number question

The digit 3 is written at the right of a certain 2-digit number forming a 3-digit number. The new number is 372 more than the original 2-digit number. What is the sum of the digits of the original ...
1
vote
3answers
63 views

Part of a proof that the product of an odd and even integers is even

I'm practicing for a test on Monday and I'm trying to do some proofs - but I'm not entirely sure if this is sufficient enough for the question. "Prove that for all integers, m and n, if m is odd and ...
5
votes
1answer
190 views

How prove that there are $a,b,c$ such that $a \in A, b \in B, c \in C$ and $a,b,c$ (with approriate order) is a arithmetic sequence?

Let $N=\{ 1,2,3,..., 3n \}$ with $n$ is a positive integer and $A,B,C$ are three arbitrary sets such that $A \cup B \cup C = N, A \cap B = B \cap C = C \cap A = \varnothing, |A| = |B| = |C| = n $. How ...