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

learn more… | top users | synonyms

4
votes
0answers
30 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?
0
votes
1answer
13 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 ...
-1
votes
2answers
274 views

Find the last two digits of the number $9^{9^9}$ [duplicate]

Find the last two digits of the number $9^{9^9}$ . [Hint: $9^9 \equiv 9 \pmod {10} $; hence, $9^{9^9}$ = $9^9+10k$ ;now use the fact that $9^9 \equiv 89 \pmod {100}$]
0
votes
0answers
56 views

Sum of digits of $x^y$

Is there any simple way to calculate the sum of digits in $x^y$ other than actually computing $x^y$ and then calculating the sum? I need to calculate this for very large numbers. Please point me if ...
0
votes
1answer
21 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
2k views

HCF, LCM, and remainders

I think this is kind of a lame problem after seeing the quality of questions on this site, but I couldn't find anything related to my question Now the basic questions is as follows, Q. Find the ...
0
votes
2answers
291 views

Running Time for Fermat's Factorization Algorithm

Let $p$ and $q$ be odd primes s.t. $p<q$ and $n= pq$. How many cycles will Fermat's Factorization produce for $n = pq$? Here is some sample data I iterated: (I am having trouble solving for an ...
6
votes
2answers
339 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 ...
2
votes
1answer
45 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 ...
2
votes
1answer
32 views

How to find a solution to the elliptic curve

We know that one solution of the given elliptic curve is (2, 1) and we have to find another rational solution such that $x$ is not equal to 2 by drawing a tangent to the curve at (2, 1). ...
0
votes
2answers
50 views

Chinese Remainder theorem, no inverse?

$$ \begin{cases} x\equiv 7&\pmod{9} \\ x\equiv4 &\pmod{12} \\ x\equiv16&\pmod{21} \end{cases} $$ Compute $m$, $9*12*21=2268$. Compute $M_1=$$m\over3$$=252$. Compute $M_2=189$. Compute ...
1
vote
2answers
14 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 ...
1
vote
3answers
46 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 ...
1
vote
1answer
36 views
+50

Are there functions that satisfy $f(km)\bmod m=f(m)$ that are not of the form $m\mapsto n\bmod m$?

For any integer $n$, consider its sequence of residues, $n\bmod1, n\bmod2, n\bmod3, \ldots$, as a function $f:\mathbb N^+\to\mathbb N$. Such a function has the following properties: $$\begin{gather} ...
1
vote
2answers
288 views

Miller-Rabin primality test, begginer reading pseudo code

I was reading Miller-Rabin primality test Wiki and I can't understand something, it says that: Now, let $n$ be prime with $n > 2$. It follows that $n − 1$ is even and we can write it as $2s \cdot ...
1
vote
3answers
38 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 ...
0
votes
0answers
30 views

Prove that there is no $n$ such that $\sigma (n)=9$ [on hold]

Prove that there is no $n\in \mathbb{N}$ such that $\sigma (n)=9$.
1
vote
1answer
14 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 ...
0
votes
0answers
27 views

Finding set of integer pairs for which two integer polynomials intersect

I am wondering if there is a theorem in number theory that addresses the following issue: Suppose we have two polynomials, f and g, with integer coefficients. Is there a general way to find elements ...
5
votes
3answers
50 views

Eisenstein integers and applications to Diophantine equations

Solve the equation $7\times 13\times 19=a^2-ab+b^2$ for integers $a>b>0$. How many are there such solutions $(a,b)$? I know that $a^2-ab+b^2$ is the norm of the Eisentein integer $z=a+b\omega$, ...
1
vote
4answers
75 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
0answers
42 views

Proving an identity involving the product of the Möbius function and Euler’s totient function.

Could anyone kindly help me to prove that $$ \sum_{d|n} \mu(d) \varphi(d) = 0 $$ for all even integers $ n \geq 2 $, where $ \mu $ is the Möbius function and $ \varphi $ is Euler’s totient function? ...
-1
votes
3answers
14 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}$
20
votes
3answers
845 views

Does an elementary solution exist to $x^2+1=y^3$?

Prove that there are no positive integer solutions to $$x^2+1=y^3$$ This problem is easy if you apply Catalans conjecture and still doable talking about Gaussian integers and UFD's. However, can this ...
2
votes
1answer
35 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
34 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 ...
5
votes
0answers
93 views
+50

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 ...
0
votes
0answers
18 views
2
votes
3answers
43 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 ...
-1
votes
0answers
21 views

How to prove the quadratic reciprocity law? [on hold]

How do you prove the quadratic reciprocity law ? I know Fermat's Little. Does that help ?
1
vote
2answers
39 views

Efficiently calculating the 'prime-power sum' of a number.

Let $n$ be a positive integer with prime factorization $p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}$. Is there an 'efficient' way to calculate the sum $e_1+e_2+\cdots +e_m$? I could always run a brute ...
0
votes
0answers
14 views

RSA and El Gamal

I was wondering if anyone knew where I could find some examples of encryption with El Gamal and RSA using very large primes? I wrote a code for El Gamal and RSA but I want to test it with some known ...
2
votes
1answer
31 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 ...
2
votes
3answers
58 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$ ...
8
votes
1answer
191 views

Olympiad problem: Erdos-Selfridge

The following problem is a special case of Erdos-Selfridge theorem: http://projecteuclid.org/euclid.ijm/1256050816 Problem: Prove that for any positive integer $n$, the product $(n+1)(n+2)...(n+10)$ ...
-1
votes
3answers
146 views

find the remainder when $19^{22}$ is divided by $92$.

find the remainder when $19^{22}$ is divided by $92$. Will Euler's totient function help us?
0
votes
1answer
310 views

Why does RSA have to use Euler's Totient function?

$$\begin{aligned}m^{ed} &\equiv m\bmod n\\ ed &\equiv 1 \bmod \phi(n)\\ \end{aligned}$$ Why does the modulus of the modular multiplicative inverse have to be the totient function? Won't any ...
28
votes
1answer
1k views

Checking a possible proof of Fermat's Last 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 ...
2
votes
2answers
89 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: ...
1
vote
1answer
28 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 ...
0
votes
2answers
28 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)$.
2
votes
0answers
23 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$. ...
-1
votes
0answers
27 views

Define $f : Z/4Z → Z/4Z$ by $f ([a]) = [3a + 1]$.

Define $f : Z/4Z → Z/4Z$ by $f([a]) = [3a + 1]$. (a) Prove that $f$ is a well-defined function. (b) Prove that $f$ is surjective. (c) Prove that $f$ is injective. I'm having trouble with this ...
0
votes
3answers
44 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 ...
3
votes
2answers
38 views

GCD Direct Proof

I need to show that if $a,b,c$ are ints such that $\gcd(a,b) = 1$ and $c|(a+b)$, then $\gcd(c,a) = \gcd(c,b) = 1$ I want to try and prove this directly because I think it will be more straightforward ...
1
vote
0answers
18 views

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

Which method should I use to calculate $-69^{-1} \mod 1313?$
5
votes
1answer
62 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 ...
4
votes
5answers
638 views

Determining the next Twin Prime?

A really simple I question I guess. Is there an algorithm or method such that given an integer $N$ there is a way to determine the next twin prime pair greater than $N$? If yes, then could you please ...
0
votes
3answers
31 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
24 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$ ...