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

learn more… | top users | synonyms

0
votes
4answers
83 views

Show that $5^n + 6^n = 0 \pmod{11}$ for all odd $n$

show that $5^n + 6^n = 0 \pmod{11}$ for all odd number $n$, but not for any even number $n$. I was not sure about this question. Do I have to pick numbers for $n$? Until I get odd number?
0
votes
2answers
90 views

number theory fibonacci

Using facts of the Fibonacci sequence, I need to show that if $m,n$ are natural numbers that satisfy $m \mid F_n$ and $m \mid F_{n+1}$, then $m=1$. I am not sure where to start with this.. I am ...
0
votes
2answers
107 views

Is 13 a Quadratic residue of 257?

Is 13 a quadratic residue of 257? Note that 257 is prime. I have tried doing it. My study guide says it is true. But I keep getting false.
0
votes
3answers
228 views

Let a|c and b|c such that gcd(a,b)=1, Show that ab|c

Let a|c and b|c such that greatest common divisor (gcd) gcd(a,b)=1, Show that ab|c.
0
votes
4answers
56 views

How to prove that if a number is divisible by two other numbers, then it is divisible by there product

I would like to prove if $a \mid n$ and $b \mid n$ then $a \cdot b \mid n$ for $\forall n \ge a \cdot b$ where $a, b, n \in \mathbb{Z}$ I'm stuck. $n = a \cdot k_1$ $n = b \cdot k_2$ $\therefore a ...
0
votes
1answer
81 views

Finding positive integer solutions to $3^x + 55=y^2$

I think it must be finite, $y$ is always even, but I don't know how to continue. edit: with $x,y\in\mathbb Z$
0
votes
5answers
91 views

Help me get the Divisor

I want to divide a particular number with $4,7,$ and $13$, but I want to get the remainder as $1,2$ and $4$ accordingly. Could you please help me get the number (If feasible at all) and please explain ...
0
votes
3answers
143 views

Finding the number of integer solutions, why is this wrong?

The question is to find the number of solutions such that $(x, y)$ are integers: $(x-8)(x-10)=2^y$. Here's what I did: $u(u-2)=2^y$. From the quadratic formula, $u=1+\sqrt{1+2^y}$. This is where I ...
0
votes
4answers
152 views

$(a,b)=d \overset{?}{\implies} (a^3,b^3)=d^3$

Why is this true? I suspect that its because $\frac{LCM(a,b)^3GCD(a,b)^3}{b^3}=a^3$ and $\frac{LCM(a,b)^3GCD(a,b)^3}{a^3}=b^3$, so it must be the case for $LCM(a,b) \notin R(a,b)$, right?
0
votes
3answers
176 views

Coprime numbers - number theory

If there is a finite set of $k$ integers how can I prove that there is a coprime for each number in the set? That is pretty obvious but what is the formal way to prove this?
0
votes
3answers
194 views

find all rational numbers p/q such that $|p/q-17/5|< 1/q^2$

This is a question in my assingment. I needto find all rational numbers p/q such that $|p/q-17/5|< 1/q^2$. Any ideas ? Thanks for any help!
0
votes
3answers
152 views

How to make something that will cap on 20?

A user on the chat asked how could he make something that would cap when it gets a specific value like 20. Then the behavior would be as follows: $f(...)=...$ $f(18)=18$ $f(19)=19$ $f(20)=20$ ...
0
votes
1answer
870 views

Why proof by induction fails for Goldbach's conjecture?

Can anyone clarify why induction method fails for this conjecture?
0
votes
4answers
3k views

Show that every ideal of the ring $\mathbb Z$ is principal

Let $\mathbb Z$ be the ring of integers. The question asks to show that every ideal of $\mathbb Z$ is principal. I beg someone to help me because it is a new concept to me.
0
votes
3answers
397 views

zero divisors and units for the group $\mathbb{Z}/n\mathbb{Z}$ with integer $n$

given the ring $ \mathbb{Z}/n\mathbb{Z} $ is always true that $ \mathbb{Z}/n\mathbb{Z}=[\text{zero divisor}]+[\text{units}] $ how can evaluate the zero divisor and units ?? I believe that $ a x=0 ...
0
votes
2answers
228 views

Solving the equation $324 x \bmod {121} = 1$

On a practice final exam (for a Computer Security course), I am given the following equation to solve, but I have no idea how to solve it: $$324x \bmod 121 = 1.$$ Any direction?
0
votes
1answer
57 views

The number of prime divisors of any number

How can one show that the number of prime divisors of any number less than $2^n$ is at most $n$.
0
votes
1answer
80 views

Is this real number an integer?

Is this real number : $$\Big(2+\frac{10}{9}\sqrt{3}\Big)^{1/3}+\Big(2-\frac{10}{9}\sqrt{3}\Big)^{1/3}$$ an integer ? I've tried different factorization, but nothing seems to work.
0
votes
5answers
108 views

Show the $(p-1)! \equiv -1 \mod p/$…

Okay so the full problem as stated is: Let $p$ be a prime number. Show that $$(p-1)! \equiv -1 \mod p.$$ I attempted to use induction, where we let p=2 be our base case then consider all primes ...
0
votes
3answers
29 views

Product of even numbers divisible by $2012$

For each positive integer $k$, $$f(k)=2\cdot 4\cdot 6\cdots2k.$$ What is the least value of $k$ for which $f(k)$ is divisible by $2012$? I tried the factorisation and LCM and I don't know ...
0
votes
5answers
160 views

Show that $n^5/5 + n^3/3 + 7n/15$ is an integer for every n [duplicate]

So far I have combined the fractions to get $ \ (3n^5 + 5n^3 +7n)/15 \ $ and that is equal to $[n(3n^4 + 5n^2 + 7)]/15$. So I need to show that $15\mid n(3n^4 + 5n^2 + 7)$. Case 1: 15 divides $n$. ...
0
votes
2answers
72 views

Let $\phi: G \rightarrow G$ be given by $\phi(g)=g^2, g\in G$. Show that if $|G|$ is odd, then $\phi$ is an automorphism

Let $G$ be an abelian group of order $|G| < \infty$. Let $\phi: G \rightarrow G$ be given by $\phi(g)=g^2, g\in G$. Show that if $|G|$ is odd, then $\phi$ is an automorphism: I consider $a ...
0
votes
4answers
130 views

Why is $n^2 - 2$ never a multiple of $3$?

I know that for any $n$, $n^2 - 2$ is never a multiple of $3$. I feel like this is a rather simple proof, but I cannot figure out how to manipulate the definition of a multiple of $3$: $n$ is a ...
0
votes
3answers
98 views

how to prove $a^{p-1} + \frac{p-1}{2\cdot 1}a^{p-2} + \frac{(p-1)(p-2)}{3\cdot 2\cdot 1}a^{p-3} + … + a \in \mathbb{Z}$?

I'm reading "Journey Through Genius, the great theorems of mathematics" by William Dunham. During the introduction of Fermat's little theorem, it explains how Euler first proved it in 1736. However I ...
0
votes
3answers
450 views

The contradiction method used to prove that the square root of a prime is irrational

The contradiction method given in certain books to prove that sqare root of a prime is irrational also shows that sqare root of $4$ is irrational, so how is it acceptable? e.g. Suppose $\sqrt{4}$ is ...
0
votes
5answers
209 views

For every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$

I'm trying to prove that for every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$. The first part of this bi-conditional was easy for me to prove, but I'm having problems with the second. Here is ...
0
votes
3answers
179 views

What is the Maths equation for positive integers? [closed]

I know there are equations for odd numbers . But is there an equation for positive integers.
0
votes
3answers
73 views

(Dis)prove that: $\forall a,b \in \Bbb Z, \space (a \mid b^2 \land a \le b) \to a \mid b$

So I'm trying disprove this statement. Well, I'm pretty sure it's wrong because it doesn't work when $a = 0$ . I'm just not sure if all I need to do is give that counterexample, or if there is a way ...
0
votes
2answers
345 views

Prove that if $a^n\mid b^n$ then $a\mid b$

Prove that if $ a^n \mid b^n $ then $a\mid b$ (without use of GCD and factorization theorem).
0
votes
3answers
2k views

If an integer is divisible by 8 and 15, then the integer also must be divisible by which of the following?

I'm not going to list the choices here, mainly because I just want the general idea. If I generalize the question and was given $n$ different integers divide some integer $r$, how do I determine what ...
0
votes
3answers
212 views

If $p$ is a factor of $m^2$ then $p$ is a factor of $m$

I'm a complete beginner and not sure where to go with this proof of Euclid's lemma. Any help would be greatly appreciated. If $m$ is a positive integer and a prime number $p$ is a factor of $m^2,$ ...
0
votes
1answer
189 views

Simultaneous equations

My question is: Solve simultaneously:(anwers are in integers) $$\begin{align} y^3 - 9x^2 + 27x - 27 &= 0 \\ z^3-9y^2+27y-27 &= 0 \\ x^3-9z^2+27z-27 &= 0 \end{align}$$ Any hints to solve ...
0
votes
2answers
81 views

What is a general way to find out whether a number obtained by a finite combination of algebraic operations is algebraic?

What is a general way to get a integers inside a radical with + or - operation(the numbers adding or subtracting each others, for example, $\sqrt5 +\sqrt7$ is this type of numbers)allow is algebraic ...
0
votes
3answers
714 views

Proving that $\gcd(ac,bc)=|c|\gcd(a,b)$

Let $a$, $b$ an element of $\mathbb{Z}$ with $a$ and $b$ not both zero and let $c$ be a nonzero integer. Prove that $$(ca,cb) = |c|(a,b)$$
0
votes
5answers
110 views

What is the remainder when $2001^{2014}$ is divided by $ 10^6$?

What is the remainder when $2001^{2014}$ is divided by $ 10^6$? I have been searching for solution on the net but seems nothing has made me understand.
0
votes
2answers
65 views

What is the upper bound for $\frac1n$ where $n$ is a prime?

What is the upper bound for $\frac1n$ where $n$ is a prime? Apparently this has something to do with repeating decimals and the period of a decimal.
0
votes
2answers
36 views

Remainder question with $6!$ and 7

Find the remainder when $6!$ is divided by 7. I know that you can answer this question by computing $6! = 720$ and then using short division, but is there a way to find the remainder without using ...
0
votes
1answer
132 views

Consider the number $n= 2^{10^{33}} +1$ [closed]

Consider the number $$n= 2^{10^{33}}+1$$ Suppose that it is known that none of the numbers $1 < k < 10^{6}$ divide $n$. Does it follow that n is a prime number? I know that the answer is a ...
0
votes
3answers
124 views

$2017$ as the sum of two squares

Write the prime $2017$ as the sum of two squares $2017$ can be written as the sum of two squares because it is a prime of the form $p\equiv 1\ ($mod $4)$ Using an appropriate algorithm find the two ...
0
votes
4answers
155 views

Suppose $(a,b)=1$, then $(2a+b,a+2b)=1\text{ or }3$.

Suppose $(a,b)=1$. Let $d=(2a+b,a+2b)$. Then $d=(2a+b)u+(a+2b)v=a(2u+v)+b(2v+u)$ where $u,v \in \mathbb{Z}$. Since $(a,b)=1$, then $a(2u+v)+b(2v+u)=1$. I'm not sure if I'm going in the right ...
0
votes
5answers
81 views

$4011x+42053 \equiv 2x-782398 \pmod {10}$

$4011x+42053 \equiv 2x-782398 \pmod {10}$ $10|(4011x+42053-2x+782398) \space \rightarrow \space 10|(4009x + 824451)$ $\rightarrow\space 4009x\equiv -824451 \pmod {10}$ I am dubious about this next ...
0
votes
1answer
55 views

Find three integer numbers such that

Find three consecutive integers such that the first is divisible by a square, the second one is divisible by a cubic and the third is divisible by a fourth power.
0
votes
5answers
107 views

Proof: $\;n^2\;$ is even if and only if $\;n\;$ is even.

Please help how would you go about doing this? I'm studying for a final. This is on a study guide. I'm having a lot of trouble with this class. Prove that $n^2$ is even if and only if $n$ is even. ...
0
votes
6answers
129 views

I have been asked this particular number theory question in an interview.

I was asked a question as such i am a shopkeeper having six weights 8,4,2,1,1/2,1/4 kg. Now i have to calculate the sum of all the possible different combinations of weights and no combinations should ...
0
votes
3answers
126 views

$a^2+b^2=0$ in a field F.

I'm not really sure how to answer this question. Prove or give a counterexample: If $F$ is a field and $a,b$ are in $F,$ then $a^2+b^2=0 \implies a=b=0$
0
votes
1answer
127 views

Divisibility of the difference of powers

Consider the following theorem: For any $a, b \in \mathbb{Z}^+$, there exist $m, n \in \mathbb{Z}$ such that $m > n$ and $a\ |\ b^m - b^n$. What's the best way to prove it? I have an idea ...
0
votes
2answers
176 views

A proof of $n*0=0$?

The only proof I've seen for this assumes that $0$ follows all the rules of arithmetic. How can we make that assumption when dividing by $0$ is a problem? I know that some people don't agree that all ...
0
votes
3answers
52 views

Construction of a 1-1 correspondence from $(-1, 1)$ to $\mathbb{R}$

Is there any function that is a 1-1 correspondence from the interval $(-1,1)$ to the set of all reals? Consider the additional caveat that the said function must also be differentiable.
0
votes
2answers
170 views

How to show $\binom{2p}{p} \equiv 2\pmod p$?

how to prove $\forall p$ prime : $\binom{2p}{p} \equiv 2 \pmod p$ we have: $\binom{2p}{p} = \frac{2p (2p-1)(2p-3)...1}{p!p!}$ but how to continue?
0
votes
4answers
181 views

Using modular congruence to solve equation

Show that there are no intergers $x$ and $y$ such that $P(x,y)=x^2-5y^2=2$ Hint from professor: Consider the equation in a convenient $\mod (n)$ so that you end up with a polynomial in a single ...