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

learn more… | top users | synonyms

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
322 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
712 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
123 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
128 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
175 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 ...
0
votes
2answers
2k views

How to perform logical inclusive OR operation on hexadecimal numbers?

In logic there is so called OR operation that is quite clear to me as long as it is in the binary system. For example, if I want to OR such binary values as "101" (which corresponds to decimal "5") ...
0
votes
2answers
285 views

Factoring for extremely large numbers that are a power of 2.

This is a variation of this question. I want to find the number of factors for a given large integer that I already know to be a power of 2. Given that the number is a power of 2, does that help by ...
0
votes
2answers
421 views

Solving quadratic residue

Suppose we have $25x^2 + 70x + 37 \equiv 0 \pmod{13}$. Since it doesn't factor we obviously have to subtract/add $(ax + b)$ from both sides of the congruence. However I'm getting different answers. ...
0
votes
4answers
568 views

Is $\gcd(a,b)\gcd(c,d)=\gcd(ac,bd)$?

Let $a$,$b$,$c$ and $d$ be four natural numbers such that $\gcd(a,c)=1$ and $\gcd(b,d)=1$. Then is it true that,$$\gcd(a,b)\gcd(c,d)=\gcd(ac,bd)$$ I'm awfully weak in number theory. Can anyone please ...
0
votes
4answers
547 views

Divisibility properties

Let $a$, $b$, $c$ be integers. Prove that if $a|b$ and $a|(b+c)$ then $a|c$.
0
votes
2answers
103 views

Prime numbers: How would you do this efficiently?

Which of the following integers is prime: 187, 287, 387, 487, or 587? I can calculate it by hand, but that would take a long time. Is there an easier way? I noticed the numbers only differ 100 from ...
0
votes
2answers
564 views

Proof that there are infinitely many Ulam numbers

This is part of self-study; this question is taken from "Discrete Mathematics and Its Applications" (Rosen). We define the Ulam numbers by setting $u_1$ = 1 and $u_2$ = 2. Furthermore, after ...
0
votes
2answers
71 views

Find the maximum value of the first number in a set

Could you help me out with a piece of homework, I really do not know, how to solve this. Even how to begin. $8$ natural numbers are written in a row. Each number, beginning from the third is a sum of ...
0
votes
2answers
322 views

Summing up all $N$ digits automorphic numbers

In mathematics an automorphic number (sometimes referred to as a circular number) is a number whose square "ends" in the same digits as number itself. Thus $5$ is automorphic since $25$ ends in ...
0
votes
2answers
426 views

Questions about algebraic identities

When people talk about algebraic identities, such as in A Collection of Algebraic Identities, are those variables appearing in them varying in $\mathbb{R}$, $\mathbb{C}$ or some even more general set? ...
0
votes
3answers
64 views

If $a,b < p$, then $p \nmid ab$?

I'm trying to prove that if there two positive integers $a$ and $b$ such that they are less than a prime number $p$, then the product $ab$ will not be divisible by $p$. I know there must be multiple ...
0
votes
6answers
72 views

Find all solutions to $a^{2003} \equiv 1 \mod{17}$

Through messing around with numbers, I found that $a \equiv 1\mod{17}$. How would you obtain this answer? Thanks!
0
votes
3answers
96 views

If the sum $\sum_{x=1}^{100}x!$ is divided by $36$, how to find the remainder?

If the sum $$\sum_{x=1}^{100}x!$$ is divided by $36$, the remainder is $9$. But how is it? THIS said me that problem is $9\mod 36$, but how did we get it?
0
votes
1answer
84 views

Integers $p,q$ such that $pq\equiv 1 \mod (p+q) $

I want to find pair of integers $p,q$ of the form: $$pq\equiv 1 \mod (p+q) $$ What have I tried so far is: Since, $pq \equiv 1 \implies p$ has inverse element with respect to $p+q$. which means ...
0
votes
3answers
79 views

if $x^2+ax+b=0$ has an integer root, show that it divides b [duplicate]

I don't know where to start. can anyone help me please ? if $x^2+ax+b=0$ has an integer root, show that it divides b
0
votes
1answer
62 views

Divisibility lemma: If $a \mid x$ and $b\mid y$ then $a + b \mid x + y$.

I remember reading about a divisibility lemma which says something like if $a \mid x$ and $b \mid y$ then $a + b \mid x + y$. Obviously this one isn't true, but what is the actual lemma I am thinking ...
0
votes
2answers
123 views

How to find the sum of positive integers $x$ and $y$, given that $ \sqrt x + \sqrt y = \sqrt {135} $?

How do you find the sum of integers $x$ and $y$ from: $ \sqrt x + \sqrt y = \sqrt {135} $? Is there a specific method that will get the answer? x and y are both positive integers. For example x ...
0
votes
4answers
63 views

Elementary Number Theory help

I missed the day we covered this in class and we have no textbook, so I'd like to know any theorem names and/or formulas used to solve the problem Prove that if $a$ is an integer then $(a^2+3a+1)^2-1$ ...
0
votes
2answers
58 views

Solving $4^{667} ≡ x \pmod{13}$ without Eulers totient theorem or CRT

Does anyone know any efficient ways to solve this without Euler's Totient Theorem or Chinese remainder theorem?
0
votes
3answers
87 views

Number of digits of $2^{1000}$ [duplicate]

A friend asks me to find the number of digits of $2^{1000}$. I tried to look for a pattern by calculating the first powers of $2$ but I didn't find it. How should I proceed? Thanks.
0
votes
1answer
87 views

If $a,b,x,y\in\Bbb N$ , and $ax-by=(a,b)$, then $(x,y)=1$

Need to prove an exercise, and for that I need to show that if $$a,b,x,y\in\Bbb N$$ and $$ax-by=(a,b),$$then$$(x,y)=1.$$ How to do this? I have no idea. Please do not use modular arithmetic.
0
votes
3answers
125 views

Euclidean algorithm

Hay I am going over some old exams and hit this: (a) Use the Euclidean algorithm to show that $\gcd(60; 17) = 1$. (b) Hence find integers $x, y$ satisfying $60x + 17y = 1$. (c) Find ...
0
votes
6answers
154 views

Exercise of divisibility of integer numbers

How to prove that if $a$ an $b$ are integers so that $3|(a^2+b^2)$, then $3|ab$?
0
votes
2answers
87 views

On the number divisors of a number

Let $d(n)$ be the number divisors of a natural number $n$. Now let $m$ be a natural number. Find least natural number $n$ such that $d(n)=m$. Thank you
0
votes
2answers
101 views

Elementary Number Theory.. If a divides..

If $a \mid (2c+3d)$ and if $-a \mid (c+d)$ then show that $3a \mid 3c$. The only progress I can say I've made is that the question is basically asking to show that $a \mid c$, because the $3$ is only ...
0
votes
2answers
174 views

Why is this not working? (Chinese remainder theorem weird result)

Trying to find $x \equiv_{17} -4$, $x \equiv_{23} 3$. OK, so $x = -4 + 17k$ for some $k$. $-4 + 17k \equiv_{23} 3$. Since $19$ is the inverse of $17 \pmod {23}$, $k \equiv_{23} (3+4)19 \equiv ...