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

learn more… | top users | synonyms

2
votes
2answers
27 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
2answers
70 views

Prove or Disprove the statement: If n∈ℤ+, then n²+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.
0
votes
0answers
29 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? The digital cube root does not seem to solve the problem.
1
vote
2answers
21 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: ...
0
votes
2answers
33 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 ...
2
votes
1answer
16 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
34 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
45 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 ...
1
vote
0answers
46 views

Count ways to reach Nth row

Given a N*M grid I need to reach last row with following operations : ...
0
votes
0answers
16 views

Converting From Different Number Systems

I've been taught to convert from base 2 to base 10 using the following process: 10110 = $0\times1 + 1\times2 + 1\times4 + 0\times8 + 1\times16 = 0\times2^0 + 1\times2^1 + 1\times2^2 + 0\times2^3 + ...
3
votes
6answers
79 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 ...
-2
votes
0answers
33 views

How to prove that 32760 is a 4-multiply perfect number?

A number $n$ is $4$-multiply perfect if $\sigma(n) = 4n$. (Compare to the definitio of perfect number, which is $\sigma(n)=2n$.) How to prove that $32760$ is a $4$-multiply perfect number?
1
vote
1answer
41 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 ...
0
votes
1answer
30 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?
7
votes
3answers
450 views

How many ways are there to write $675$ as a difference of two squares?

How many ways are there to write the number $675$ as a difference of two squares? Is there a way to generalize this?
0
votes
4answers
88 views

How can we find the smallest number $n$ such that $2^{2^n} + 1$ is not a prime.

How can we find the smallest Fermat number (i.e. in the form $2^{2^n} + 1, n \in \mathbb N$) that is not prime and show that it is indeed not a prime? Yes, when $n=5$, it is not a prime. How can we ...
2
votes
2answers
949 views

Understanding mathematical induction for divisibility

I'm on my quest to understand mathematical induction proofs (beginners). First, thanks to How to use mathematical induction with inequalities? I kinda understood better the procedure, and practiced it ...
3
votes
0answers
69 views
+100

How to represent Fermat number $F_n$ as a sum of three squares?

Let $F_n=2^{2^n}+1$ be the Fermat number. How to represent the Fermat number $F_n$ for $n \geq 3$ as a sum of three squares of different natural numbers? For example for $n=3$ we have $$ ...
0
votes
1answer
43 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
3answers
49 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 ...
1
vote
2answers
27 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
4answers
3k views

the cube of integer can be written as the difference of two square

This Exercise $4$, page 7, from Burton's book Elementary Number Theory. Prove that the cube of any integer can be written as the difference of two squares. [Hint: Notice that ...
3
votes
2answers
62 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
1answer
39 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 ...
2
votes
3answers
2k views

Rules of Division

I know a few rules number ends with even digit, it is divisible by 2 number ends with 5 or 0 is divisible by 5 if sum of all digits in a number is divisible by 3 then that number is divisible by 3 ...
2
votes
1answer
39 views

Concerning types of square-free numbers and comparing sizes of their subsets.

Call a square-free a 2-prime if it has exactly two prime divisors. Call a square-free a 3-prime if it has exactly three prime divisors,etc. Does there exist an integer sufficiently large N such that ...
0
votes
1answer
18 views

Division Algorithm With Negative and Absolute Value

(a) Prove that $d \, |\, a$ implies that $d \,| (−a)$. (b) Prove that $d\, |\, a$ if and only if $d \,| (−a)$. (c) Prove that $d \,|\, a$ if and only if $d\, \Big|\, |a|$. I can see why these ...
1
vote
3answers
45 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)$, ...
0
votes
1answer
28 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
57 views

fundamental theorem of arithmetic problem

Change machine contains n quarters, 2n nickels, 4n dimes, n positive integer. Find all values of n so that these coins total k dollars, k positive integer. My thinking is to reduce coins to prime ...
0
votes
2answers
75 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?
0
votes
2answers
55 views

Making 24 with given number N

Initially we have a sequence of n integers: 1, 2, ..., n. In a single step, we can pick two of them, let's denote them a and b, erase them from the sequence, and append to the sequence either a + b, ...
2
votes
1answer
76 views

A question about how to express a fraction as ${1\over q_1}+{1\over q_2}+ \cdots+{1\over q_N}$

Let $x$ be a positive rational number, strictly between $0$ and $1$. Prove that there is a finite strictly increasing list of positive integers $2 \leq q_1<q_2<\cdots<q_N $ such that ...
1
vote
2answers
22 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 ?
2
votes
0answers
28 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
0answers
54 views

Mordell Diophantine: $x^2+11=y^3$

I've been trying to solve the diophantine $$x^2+11=y^3$$ recently but to no avail. I tried the "UFD trick", re-writing as $(x-i\sqrt{11})(x+i\sqrt{11})=y^3$, but it didn't give me all the solutions. I ...
0
votes
0answers
12 views

Looking for general proof of a sum of an additive form of elementary symmetric polynomials

For sake of avoiding complicated general formulation I try to formulate in the special case of a set of 3 numbers $M=\{a_1,a_2,a_3\}$ with e.g. $a_i\in\mathbb R$. The sum I am looking for is in this ...
1
vote
2answers
210 views

A problem for math lovers to count the digits

Today a classmate of mine asked a question which is based on counting. Question. Find a positive integer which when multiplied up to $6$ times will give numbers having the same digits but rearranged ...
10
votes
2answers
527 views

What is the remainder when $1! + 2! + 3! +\cdots+ 1000!$ is divided by $12$?

What is the remainder when $$1! + 2! + 3! +\cdots+ 1000!$$ is divided by $12$. I tried to do it using binomial theorem but that doesn't help. How will we do this? Please help.
13
votes
4answers
566 views

Proving that e is irrational

Prove that that e is irrational. Recall that e $=\sum_{n=0}^\infty\frac{1}{n!}$, and assume $\mathrm{e}$ is rational. Then $$\sum\limits_{k=0}^\infty \frac{1}{k!} = \frac{a}{b}\quad \text{for some ...
1
vote
3answers
114 views

Look at the following infinite sequence: 1, 10, 100, 1000, 10000, . . ..

What is the proof that there are 2 numbers in this sequence that differ by a multiple of 12345678987654321?
6
votes
3answers
1k views

Expression of an Integer as a Power of 2 and an Odd Number (Chartrand Ex 5.4.2[a])

Let $n$ be a positive integer. Show that every integer $m$ with $ 1 \leq m \leq 2n $ can be expressed as $2^pk$, where $p$ is a nonnegative integer and $k$ is an odd integer with $1 \leq k < ...
0
votes
1answer
28 views

How can we show that $\pi (x) \leq \frac{x}{2}+1$?

What is the proof that the prime counting function $\pi (x)$ is such that $$\pi (x) \leq \frac{x}{2}+1$$
6
votes
4answers
851 views

Can any two irrational numbers NOT of the form (m+A) and (n-A) be added to produce a rational number?

$m$ and $n$ being rational numbers, A being an irrational number. I was wondering if two irrational numbers when added always yield an irrational number. All the counter-examples I could find were of ...
5
votes
3answers
239 views

What is the smallest natural number n?

What is the smallest natural number n for which there is a natural k, such that, the lasts 2012 digit in the representation decimal of $n^k$ are equal to 1? I don't even know how to start with it ... ...
2
votes
3answers
27 views

Remainder problem when dividing numbers

The number x is a positive integer < 100. When x is divided by 7, the remainder is 2, and when x is divided by 10 the remainder is 8. What is the value of x? Is there a formula to solve this type ...
4
votes
4answers
259 views

Solving Diophantine equations involving $x, y, x^2, y^2$

My father-in-law, who is 90 years old and emigrated from Russia, likes to challenge me with logic and math puzzles. He gave me this one: Find integers $x$ and $y$ that satisfy both $(1)$ and $(2)$ ...
0
votes
1answer
40 views

If $\gcd (a,0)=1),$ what can a possibly be?

I feel like a could be any number, but $0$ could divide any number,so they won't be mutually exclusive. I'm not sure, maybe this is not related, but it just confused me.
1
vote
1answer
25 views

Finding a nontrivial solutions in natural numbers.

Consider the equation for natural numbers $i,j,k,l:$ $$ (j^2-i^2) (k\cdot l)^2=2\, (l^2-k^2) (i\cdot j)^2. $$ I am trying to prove that it has no solution. To undertand why, let us first consider ...
-1
votes
0answers
28 views

Number 36 in base 4/5 [on hold]

In my curse of number theory I need write the integer number 36 in base $4/5$. I have been researching how to do it but do not make it yet. Appreciate if you can help me