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

learn more… | top users | synonyms (1)

15
votes
1answer
282 views

$a^b+2$ or $a^b-2$ is in set

Let $A$ be an infinite set of positive integers. For any two $a,b\in A$, $a\neq b$, at least one of the numbers $a^b+2$ and $a^b-2$ are also in $A$. Must $A$ contain a composite number?
1
vote
1answer
41 views

Calculating point 2P on an elliptic curve

The equation for the curve is $$y^2=x^3+ax+b$$ and the point in question is $P(x,y)$. We have to verify that the $x$ coordinate of $2P$ is $(x^4-2ax^2-8bx+a^2)/4y^2$. However, the value I get is $(9x^...
1
vote
2answers
203 views

Converting equation into Weierstrass form

I have to convert the equation $y^2 +xy +y=x^3 $ by a change of linear variables to the form $Y^2=X^3+aX+b$ where $a$ and $b$ are rational numbers. So far, by completing the square method I've reduced ...
0
votes
1answer
111 views

Properties of the greatest common divisor: $\gcd(a, b) = \gcd(a, b-a)$ and $\gcd(a, b) = \gcd(a, b \text{ mod } a)$

Prove that (a) gcd(a, b) = gcd (a, b – a) (b) Let r be the remainder if we divide b by a. Then gcd(a, b) = gcd(a, r). I solved part a like: Assume a=pcommonpa b=pcommonpb gcd (a,b) = ...
1
vote
2answers
36 views

Order of elements in a commutative/abelian group

Prove that if $(G, ◦)$ is a (not necessarily finite) commutative group, and if $g$ and $g'$ are members of $G$ which have finite orders (say $ω$ and $ω'$ respectively), then $g ◦ g'$is of finite order....
1
vote
3answers
58 views

Two questions on number 2013

a) All natural numbers from $1$ to $2013$ are written in a row in an order. Can you insert '+' and '-' signs between them so that the value of the resulting expression is zero? If it is so how many '+'...
6
votes
2answers
385 views

Quadratics with roots as integers; possible values of a

Suppose $a$, $b$ are real numbers such that $a+b=12$ and both roots of the equation $x^2+ax+b=0$ are integers. Determine all possible values of $a$. I don't know how to go about doing this without ...
0
votes
1answer
348 views

Use mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes.

Use strong mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes. I know the steps of weak mathematical induction... Basis step: $p(n)$ for $n=1$ or any ...
1
vote
3answers
120 views

Problem regarding proving a permutation group

The question states: Show that the set of permutations of three objects form a group. Give the multiplication table for this group. If we take three distinct objects, the set of the ...
3
votes
2answers
84 views

Are these two definitions of the natural numbers equivalent?

If we consider two definitions of the natural numbers: Definition 1 $N$ is the set that satisfies all of: There is an element $0$ in $N$. For each element $n$ in $N$, there is the successor of $n$,...
2
votes
1answer
77 views

Find the chance that $a^3 + b^3 \equiv 0 (\mod 3)$

We are given set of integer numbers $\{1,2, \dots N\}$. $N \ge 3$ Then perform a drawing with replacement of two elements $a$ and $b$. Problem is to find the probability of following statement holding ...
1
vote
1answer
30 views

Question on Sum of Divisor?

I know $\sigma(m)=24$ for $m=\{14,15,23\}$ but how can we find this numbers? Here is what I did Let the prime factorization of $m$ be $$m=p_1 ^{\alpha _{1}}p_2 ^{\alpha _{2}}\cdot\cdot\cdot p_k ^{\...
-1
votes
3answers
18 views

common solution to $x\equiv 2^{2001}\pmod{4}$ and $x\equiv 14^{2001}\pmod{25}$

How to find the common solution to $x\equiv 2^{2001}\pmod{4}$ and $x\equiv 14^{2001}\pmod{25}$
1
vote
4answers
107 views

Last 2 digits of $\displaystyle 2014^{2001}$

How to find the last 2 digits of $2014^{2001}$? What about the last 2 digits of $9^{(9^{16})}$?
1
vote
1answer
75 views

Solving $x^3 + 2x^2 + 5 = 0 \mod 7.$

I'm doing a number theory problem, and I've reduced it to solving $x^3 + 2x^2 + 5 = 0 \mod 7.$ Is there any way to simplify this and solve it in a prettier way than brute force?
0
votes
2answers
43 views

Hexadecimal Representation

Find the last digit of the hexadecimal representation of the number (in decimal notation) $$1+10+10^2+10^3+\cdots+10^{100}$$ I calculated the sum of the series above using GP and obtained $\frac{10^{...
2
votes
3answers
75 views

$(a\mod m)/(b\mod m) = (a/b)\mod m$?

b and m are relatively prime (m is prime and $b \in \mathbb Z_m^* $). In truth, I would like to be able to get to the following point (it is a simplified example): $\frac{ab \mod m}{b \mod m} = a \...
3
votes
1answer
42 views

Can we tell if a number is prime by the number of its partition ?

Can we tell if a number is prime by the number of its partition ? Or in general, how much can we know about a number itself from its partition function ? I understand that Ramanujan has some ...
0
votes
1answer
51 views

Solutions of $a^{2} - 2b^{2} \equiv 0$ mod $p$

I came across this question in attempting to find $p$ for which $\mathbb{Z}_{p}[\sqrt{2}]$ is a field. Consider the equation: $$a^2 - 2b^2 \equiv 0 \enspace \text{mod p}$$ For which primes $p$ is ...
2
votes
0answers
211 views

Which integers are a sum of two relatively prime squares?

It's well known that a positive integer $n$ is a sum of two squares if and only if every prime of the form $4m + 3$ that divides $n$ appears with even multiplicity in the prime factorization of $n$. ...
0
votes
2answers
70 views

If $a \equiv b \bmod n$, then $\gcd(a, n)= \gcd(b,n)$ [duplicate]

Again, I have been stuck in a problem of modular arithmetic. Given that $a,b, n \in \mathbb Z $ and $n>0$ and $a \equiv b \bmod n$. Show that $\gcd(a, n)= \gcd(b,n)$.
33
votes
1answer
2k views

Checking a Proof of a Theorem

Theorem 1.2 of Bennett and Skinner (Canad. J. Math., 2004) asserts that the Diophantine equation $x^{p} - 4y^{p} = z^{2}$ is unsolvable for every prime $p \geq 7.$ The following is a possible proof ...
3
votes
2answers
59 views

GCD Direct Proof

I want to try and prove this directly because I think it will be more straightforward then a indirect. Also, I believe this has something to do with relatively prime numbers. The help is appreciated!
1
vote
3answers
69 views

If $\gcd(a,b) = 1,$ then why is the set of invertible elements of $\mathbb Z_{ab}$ isomorphic to that of $\mathbb Z_a\times \mathbb Z_b$?

If $\gcd(a,b) = 1,$ then why is the set of invertible elements of $\mathbb Z_{ab}$ isomorphic to that of $\mathbb Z_a\times \mathbb Z_b$? I know the proof that as rings, $\mathbb Z_{ab}$ is congruent ...
1
vote
0answers
39 views

How to calculate -69^(-1) mod 1313

Which method should I use to calculate $-69^{-1} \mod 1313?$
0
votes
1answer
48 views

Let $\gamma$ be the Euler-Mascheroni constant. Can there be natural numbers $a,b,c$ such that $\log a - \log b - \log \log \log c =\gamma$?

Can there be integers satisfying $$\ \log a - \log b - \log \log \log c = \gamma \ \ \ ? $$
7
votes
1answer
109 views

Last three digits in number $1^{2013} + 2^{2013} + 3^{2013} + … + 1000^{2013}$

I'm trying to find the last three digits in number $1^{2013} + 2^{2013} + 3^{2013} + ... + 1000^{2013}$. I started by calculating the remainder for even numbers, since I can present even numbers as $2^...
3
votes
0answers
63 views

Multiple of $n$ and the sum of its digits is $k\geq n$.

Show that for every positive integers $k\geq n$, with $n$ not divisible by $3$, there is a positive integer divisible by $n$ and such that the sum of his digits is $k$.
0
votes
1answer
29 views

Show that $\mathbb{Z} [\sqrt p]$ is an ordered Integral Domain.

Let $\mathbb{Z}[\sqrt p]=\{ a+b\sqrt p ~| a,b\in \mathbb{Z},p~is~prime\} $ Assume $\mathbb{Z}[\sqrt p]$ ia an integral domain with usual addition and multiplication. Show $\mathbb{Z}[\sqrt p]$ is an ...
0
votes
3answers
59 views

proof of divisibility of n(n+1)(2n+1) by 6 [duplicate]

How can I prove that $n(n+1)(2n+1)$ (where $n$ is a positive integer) is divisible by 6? As the product is even it is divisible by 2. But I do not know how to prove that it is divisible by 3
5
votes
3answers
562 views

Which rational primes less than 50 are also Gaussian primes?

Which rational primes less than 50 are also Gaussian primes? My attempt: First we need to list all of the rational prime numbers that are less than $50$ $1,2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,...
0
votes
3answers
51 views

if $m>n$ prove that $ a^{2^n} + 1$ is a divisor of $a^{2^m} - 1$

Stuck on this question without much progress. Problem no 49. Section 1.2 Niven. Any hints in the right direction ? For the second part : How can I use this to find $gcd(a^{2^m}+1,a^{2^n}+1)$ ?
1
vote
0answers
31 views

Composite residuosity statement.

Consider the following definition. A number $z$ is said to be $n$-th residue modulo $n^2$ , if there exists a number $y \in \mathbb{Z}_{n^2}^*$ such that $$z\equiv y^n \mod n^2$$ Let us take $n=6$ ...
2
votes
1answer
878 views

Finding the number of divisible integers in the range $[1, 1000]$.

Sorry if this is a stupid question. I am asked to find the number of positive integers in the range $[1, 1000]$ that are divisible by $3$ and $11$ but not $9$. Here's how I $\text{tried}$ to do it. ...
4
votes
1answer
74 views

Solve $x^4 - 2x^3 + x = y^4 + 3y^2 + y \wedge (x,y) \in \mathbb{Z}^2$

I want to solve equation $x^4 - 2x^3 + x = y^4 + 3y^2 + y$ in integers. The task comes from the LXVI Polish Mathematical Olympiad. Series with this task ended twenty days ago, so it is legal to talk ...
0
votes
2answers
34 views

Show that for any integer not divisible by 2 or 5, there is a multiple of it which is a string of 1s. [duplicate]

Given that a number $n \equiv\{1,3,7,9\} \pmod{10} $ show that there is a multiple of $n$, $q$ that is a string of consectutive $1$s.
2
votes
2answers
102 views

$(a,b)[a,b]=ab$ in non factorial monoids

Do you know of a proof of $[a,b](a,b)=ab$ in $\mathbb Z$ that doesn't use prime factorization? To be more precise let's strip all unnecessary properties and leave only the bare bones of divisibility: ...
0
votes
2answers
32 views

$\gcd(a,n)=d$ and $s,t$ solutions to $ax\equiv b \pmod{n}$ then $s\equiv t\pmod{n/d}.$

If $\gcd(a,n)=d$ and $s,t$ are each solutions to $ax\equiv b\pmod{n}$ then $s\equiv t \pmod{n/d}$. As $d\mid a$ say $a=dm$ and as $s,t$ are each solutions, $as\equiv at\pmod{n}$ so $$a(s-t)=nk \text{...
2
votes
0answers
61 views

Convergent sum of reciprocals?

Let n denote a positive integer and let $\sigma(n)$ denote the sum of all divisors of $n$, so that $\sigma(n)$ is larger than $n$ (for $n > 1$) but not by much since it's bounded above by $c\ ...
3
votes
1answer
102 views

New Identities for Generalized Fibonacci Numbers?

Over the past few months I have been investigating one the generalizations of the Fibonacci numbers, called the Generalized Fibonacci Numbers (GFNs). The GFNs are just like the regular Fibonacci ...
10
votes
0answers
222 views

Number of ways to express a binary number in a certain way

So I'm working on a problem where I get to a point where I have to count the number of solutions to an equation or at least find a decent upper bound to be used in an estimate I need later. The ...
2
votes
0answers
35 views

Repeated application of interesting function on tuples

This question was inspired by Thursday's CIMC. Suppose you have a function $$f_n: (\Bbb{Z}/n\Bbb{Z})^n\to(\Bbb{Z}/n\Bbb{Z})^n; (a_1,a_2,a_3,\dots,a_n)\mapsto (b_1,b_2,b_3,\dots,b_n)$$ defined as ...
2
votes
3answers
145 views

Prove that $ 2^n \not \equiv 1 \pmod{n} $ for any $n > 1$.

I have proved this in following way. Assume that $ 2^n \equiv 1 \pmod{n} $. that means $n\mid(2^n -1)$. but by proof by contradiction, for $n=3$ this does not hold and we can say $n \nmid (2^n-1) ...
19
votes
2answers
556 views

Does this system of simultaneous Pell-like equations have any non-trivial positive integer solutions?

Let $a,b,c$ be positive integers satisfying \begin{align} 2a^2-1 &= b^2, \\ 2a^2+1 &= 3c^2. \end{align} The trivial solution is $(a,b,c)=(1,1,1)$. Are there others?
3
votes
3answers
164 views

find the last two digits of $2^{250}$.

Suppose we want the last two digits of $3^{250}$, one can use the theorem $a^{\phi(n)}\cong 1(\mod n)$ whenever $(3,n)=1$. But instead, if i have $2^{250}$, how do i solve this problem, because here $(...
2
votes
2answers
179 views

$Ax+By+Cz=D \text { has a solution iff } \gcd(\gcd(A,B),C)\mid D$ [duplicate]

I read today that $Ax+By+Cz=D \text { has a solution iff } \gcd(\gcd(A,B),C\mid D$ but I can't find it again, I also can't find any Diophantine equations with 3 variables that doesn't have solutions ...
1
vote
1answer
338 views

An effcient method of solving a Diophantine equation with 3 variables $Ax+By+Cz=D$?

I'm trying to make an efficient algorithm to find one of the solutions and how many solutions there are to the equation $$Ax+By+Cz=D$$ where $A,B,C,D\in \mathbb Z$ and the range for $x,y,z\in \mathbb ...
1
vote
2answers
81 views

Maximum GCD of two polynomials

Consider $f(n) = \gcd(1 + 3 n + 3 n^2, 1 + n^3)$ I don't know why but $f(n)$ appears to be periodic. Also $f(n)$ appears to attain a maximum value of $7$ when $n = 5 + 7*k $ for any $k \in \Bbb{Z}$. ...
2
votes
2answers
94 views

Find all solutions of the equation $n^m=x^2+py^2$ which satisfy the following properties

Prove or disprove that, There always exists a solution of the equation, $$n^m=x^2+py^2$$ with odd $x$ and $y$ and for all $m\geq k$ for some positive integral $k$. Here $p$ is an odd prime and $n\...
6
votes
1answer
76 views

How to solve the following equation in $\mathbb{Z}_n$?

Given an $n\in\mathbb{N}$, $a\in \mathbb{Z}_n$ and $x,y\in\mathbb{Z}$, how do I approach to solving the following equation: $a^x \equiv a^y \mod n$ I think that from here I can deduce that: $x \...