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

learn more… | top users | synonyms

0
votes
0answers
24 views

Modular equations

$$ x^{13}\equiv4\pmod{101}\\x\equiv5^{5^{5^{5}}}\pmod{47\cdot27} $$ Equations are separate. How should I approach these? Both has something to do with Euler's theorem, I believe, but all my attempts ...
6
votes
0answers
37 views

Factorial division and remainders: 100!+102! mod 100

I'm having some issues with factorial division. I've been asked to determine the remainder of $11!$ under division by $12$. My logic was to state that $11! = 1\cdot2\cdot3\cdot4\cdots$ stopping there ...
1
vote
1answer
30 views

Find all non-negative integers $n,k$ such that ${n \choose k }=143$?

How does one find all non-negative integers $n,k$ such that ${n \choose k}=143$? I factorized into $143=11 \cdot 13$, which means that $11 \cdot 13=\frac{n!}{k!(n-k)!}$, which implies that $n!=11 ...
-3
votes
0answers
24 views

How to prove that $ \left( {2^n - 1} \right)^2$ divides ${2^{\left( {2^n - 1} \right)n} - 1}$? [on hold]

How to prove that $\displaystyle \left( {2^n - 1} \right)^2$ divides $\displaystyle {2^{\left( {2^n - 1} \right)n} - 1}$ ?
0
votes
2answers
29 views

Show that $b^{2^n}+1$ is a factor of $b^{2^m}-1$.

Let $m$ and $n$ be natural numbers such that $m>n$ and $b$ be any integer Show that $b^{2^n}+1$ is a factor of $b^{2^m}-1$.
2
votes
2answers
57 views

If $a+1/a$ is an integer, then so is $a^t+1/a^t$ for $t\in\mathbb N$

I need to show if $a$ is in $\mathbb{R}$ but not equal to $0$, and $a+\dfrac{1}{a}$ is integer, $a^t+\dfrac{1}{a^t}$ is also an integer for all $t\in\mathbb N$. Can you provide me some hints please?
7
votes
0answers
47 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
17 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 ...
0
votes
2answers
28 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 ...
2
votes
1answer
33 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). ...
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
47 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
348 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 ...
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$.
2
votes
1answer
47 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
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 ...
5
votes
3answers
51 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
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}$
1
vote
4answers
80 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})}$?
0
votes
0answers
46 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? ...
2
votes
1answer
40 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 ...
0
votes
0answers
18 views

Find the number of solutions $k$ to the equation $m \lvert (n\cdot k)$, modulo $m$

I have no idea how to approach this. Any hints?
-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 ?
2
votes
3answers
44 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 ...
0
votes
0answers
15 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
32 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 ...
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 ...
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$. ...
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)$.
-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 ...
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 ...
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 ...
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 ...
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 ...
0
votes
0answers
28 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 ...
0
votes
1answer
17 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
48 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
2
votes
3answers
59 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
vote
0answers
17 views

Number of solutions to $x^n \equiv a \pmod{2^b}$.

I've been trying to prove the following statement: Let $m \in \mathbb{N}$ and let $2^k$ be the highest power of 2 that divides $m$. Further, let $a$ be an odd integer such that $x^m \equiv a ...
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$ ...
2
votes
1answer
37 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. ...
0
votes
2answers
28 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
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: ...
0
votes
2answers
19 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 ...
2
votes
0answers
39 views

Convergent sum of reciprocals?

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

Prove $2^n \not\equiv 1 \pmod{n}$ for $n>1$ [duplicate]

Prove that $2^n \not\equiv 1 \pmod{n}$ for $n>1$. I'm asking for any advice.