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

learn more… | top users | synonyms

1
vote
0answers
7 views

Representing a product of orbits as a disjoint union of orbits

Let $A$ be a finite abelian group, and let $B$ and $C$ be subgroups. In the $A$-set $A/B\times A/C$, the stabilizer of any element is $B\cap C$, so we know there is a decomposition of $A$-sets like ...
0
votes
0answers
10 views

$g^{2k} \equiv g^i \pmod{p} \implies 2k \equiv i \pmod{p-1}$?

Why does $$g^{2k} \equiv g^i \pmod{p}$$ imply that $$2k \equiv i \pmod{p-1}$$ when $p$ is some prime and both $i$ and $k$ are $\in \{0, 1, \dots , p-1\}?$
1
vote
0answers
41 views

Where can I get full list of giuga numbers discovered so far?

I want full list of giuga numbers discovered so far , on googling i found this list. But it is not a complete list? Where can I get them ? Or is there any non-brute force generating algorithm for ...
0
votes
0answers
17 views

Given $p=(m+n)/(u+v)$, express $p$ in terms of $m/u$ and $n/v$

Given $p=(m+n)/(u+v)$, express $p$ in terms of $m/u$ and $n/v$. My attempt; dividing numerator and denominator by $uv$ we obtain $p=((m/u)*1/v+(n/v)*1/u)/(1/u+1/v)$ but am stuck here
-6
votes
1answer
40 views

Divisibility in The Integers [on hold]

For $n\ge1$, establish each of the following using induction or congruences: $$8\mid 5^{2n}+7$$ $$15\mid 2^{4n}-1$$$$5\mid 3^{3n+1}+2^{n+1}$$$$21\mid 4^{n+1}+5^{2n-1}$$$$24\mid 2\cdot7^n+3\cdot5^n-5$$ ...
-5
votes
3answers
30 views

Question from no. theory [on hold]

For $n \ge 2$ , use congruence theory to establish each of the following divisibility statements: $$a)7|5^{2n} + 3.2^{5n-2}$$ $$b)13|3^{n+2} + 4^{2n+1}$$ $$c)27|2^{5n+1} +5^{n+2}$$ ...
0
votes
0answers
32 views

Conjecture: three or more decompositions into powers with a base differing by 1 means its a perfect power

All the following terms are positive integers. If $$(i_1)^{a_1}(i_1+1)^{b_1}=n $$ $$(i_2)^{a_2}(i_2+1)^{b_2}=n $$ $$(i_3)^{a_3}(i_3+1)^{b_3}=n $$ then $n$ is a perfect power, i.e. it is expressible ...
0
votes
3answers
17 views

Nonzero quadratic residues modulo 101

How many Nonzero quadratic residues are there modulo prime 101 I am lost where to start to my knowledge there is no formula for number of quadratic residues a prime has It will be too much to start ...
1
vote
0answers
38 views

Single expression that must be satisfied by large twin primes, is it possible to use it to prove infinity of twin primes [on hold]

http://vixra.org/pdf/1411.0579v1.pdf http://vixra.org/pdf/1410.0112v1.pdf In these two papers for any pair of twin primes $p,p+2$, larger than $3$ and $5$, I have derived an expression $u$ that must ...
1
vote
3answers
94 views

Solving $2^x \equiv x \pmod {11}$

Solve $ 2^x \equiv x \pmod {11}$. I know 2 is a primitive root modulo 11. So. I get $x \equiv \operatorname{ind}_2x \pmod {10}$ And I'm stuck! (Maybe I can $x=1$, $x=2$, $x=3$, and so on... ...
1
vote
3answers
55 views

$ (3+\sqrt{5})^n+(3-\sqrt{5})^n\equiv\; 0 \; [2^n] $

Proof that for all $n\in \mathbb{N}$ : $$ (3+\sqrt{5})^n+(3-\sqrt{5})^n\equiv\; 0 \; [2^n] $$
3
votes
1answer
41 views

The order of element in $\mathbb{Z} / 2^{2014}\mathbb{Z}$

Find the smallest integer $n$ such that $2^{2014}|17^n-1$. i.e. Find the order of $17$ in $(\mathbb{Z}/ 2^{2014} \mathbb{Z})^{\times}$. I think we have to use the lifting the exponent lemma: If ...
2
votes
1answer
26 views

When is $\frac{n-13}{5n+6}$ Reducible?

Find the least positive integer n for which $\frac{n-13}{5n+6}$ is a non-zero reducible fraction. I've just begun working with NT problems, and I'm not quite sure how I should approach this without ...
1
vote
2answers
56 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
1answer
54 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
39 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
32 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
31 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
82 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
57 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
22 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
30 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
34 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
15 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
49 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
353 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
48 views

Use mathematical induction to prove that any integer n>=2 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
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
49 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
53 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
34 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
29 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
39 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
45 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?$