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

learn more… | top users | synonyms (1)

2
votes
3answers
44 views

Get integer solutions for $13x\equiv1\pmod{60}$ by euclidean method

I am now studying the RSA algorithm. The keypair generation equation of RSA is $d*e = 1 \pmod{(n-1)(q-1)}$ (where d, e is public key private key each other) In this situation I got the private key$= ...
0
votes
0answers
29 views

Odd Divisor Numbers in a Range not starting at 1

How can we find, given a range of numbers, how many of those numbers have odd divisors? After some searching, I noticed that perfect squares have this nature only. However, this is only if you start ...
0
votes
1answer
26 views

$x^{(p-1)/d}$ takes d distinct values

Im working on this Exercise I can do do part b) but Im stuck on part c). I know that if $e$ is a positive factor of $p-1$ then the equation: $$X^e \equiv 1 \quad \textrm{mod p} $$ has exactly $e$ ...
1
vote
2answers
67 views

Show that $5\mathbb{Z}-5\mathbb{Z}=5\mathbb{Z}$.

My proof. Lemma. $\mathbb{Z}-\mathbb{Z}=\mathbb{Z}$. Proof. ($\Rightarrow$) Let $z\in \mathbb{Z}-\mathbb{Z}$. Then, there is $z_{1},z_{2} \in\mathbb{Z}$ such that $z=z_{1}-z_{2}$. So, ...
0
votes
0answers
25 views

Mapping between different groups

Given $y = g^x$ $mod$ $p$ (assume we cannot calculate $x$ from $y$), is there a way to find $y'$ s.t., $y' = g^x$ $mod$ $p'$? Is this a DDH problem?
4
votes
1answer
34 views

On factoring and integer given the value of its Euler's totient function.

In an entrance test for admission into an undergraduate course in mathematics the following question was asked. Consider the number $110179$ this number can be expressed as a product of two distinct ...
0
votes
1answer
23 views

Numbers question HCF

P is a positive integer such that it is less than 400. Given that 15 is the Highest common factor of 45 and p , find two possible values of p. This type of my question is my biggest problem . Can I ...
0
votes
1answer
37 views

Finding an upper bound for a sum over primes

Fix $X>\geq 1$ a real number and let $1\leq y<X.$ Is there a positive constant $B$ such that $$\prod_{y<p\leq X} \left(1+\frac{3}{p}+ \sum_{\nu \geq 2} \frac{(\nu+1)^2}{p^{\nu}}\right)\leq ...
0
votes
1answer
62 views

When and why does this divide?

I've been working a lot with forms of this type, $\lfloor\frac{f}{g}\rfloor-\lfloor\frac{f-1}{g}\rfloor=1$ if $g|f$ and $0$ otherwise. This is valid for any expression $f$ and $g$ of natural numbers ...
1
vote
0answers
53 views

Given a group of numbers, get a given value?

I have been thinking about a better solution to the following problem: Given a group of numbers, tell if it is possible to get some value, by multiplying all the numbers by $\{0,1,-1\}$ and then ...
1
vote
1answer
71 views

How do I prove the following result in number theory? [closed]

There exist no $(n, m) ∈ \mathbb{N}$ so that $n + 3m$ and $n ^2 + 3m^2$ both are perfect cubes.
2
votes
2answers
105 views

Express a prime $p$ as $p=a^2-2b^2$

Suppose $2$ is a quadratic residue modulo $p$ for an odd prime $p$. That is, there is an element $u$ such that $u^2 \equiv 2 \pmod{p}$. From here, can we prove that there exist integers $a$ and $b$ ...
0
votes
3answers
46 views

How to tell if number is natural?

I'm making a test, and there's a question: "Which one of the given expresions, takes value which is natural number". $a) \frac{17}{21} + \frac{12}{42}$ $b) \frac{\sqrt{64}}{\sqrt{8}}$ $c) ...
2
votes
3answers
122 views

Show that $5\mathbb{Z}+3\mathbb{Z}=\mathbb{Z}$

I showed this: $5\mathbb{Z}+5\mathbb{Z}=5\mathbb{Z}$. i.e., $5\mathbb{Z}+5\mathbb{Z}=5(\mathbb{Z}+\mathbb{Z})$. So, since we know $\mathbb{Z}+\mathbb{Z}=\mathbb{Z}$, ...
2
votes
1answer
39 views

Congruent modulo and primes

I have the integer $m \geq 2$ and the statement $(*)$ For all integers $a$ and $b$, if $ab \equiv 0 \ (\text{mod } m)$, then $a \equiv 0 \ (\text{mod } m)$ or $b \equiv 0 \ (\text{mod } m)$ I need ...
3
votes
1answer
115 views

Solutions of equation $y^5+1=x^2 $

Working in $\mathbb{Z}^2$. I am trying to prove that there is no solution $$x\equiv3\mod4$$ for $|x|\geq 2$. I already know $5|x$ and $x$ is odd.
2
votes
2answers
72 views

Odd binomial sum equality has only trivial solution?

Suppose $$\sum_{k\ {\rm odd}}^n {n \choose k} 2^{(k-1)/2} = \sum_{k\ {\rm odd}}^m {m \choose k} 2^{(k-1)/2} 3^{(m-k)/2}.$$ Does $m=n=1$? Clearly $m \leq n$, and for every $n$ there is at most one ...
4
votes
1answer
21 views

Finding Integer solutions to non homogenous equation

I'm not sure about how to tackle this: $77x^{12}-49y^{12}+2z^{12}=63xyz^{10}$ When considering this equation modulo 7 a few times, it would seem that an "infinite descent" of each variable having 7 ...
-1
votes
0answers
14 views

Let G be a group with identity ε. If a, b ∈ Z and x ∈ G are such that x a = ε and x b = ε then show that x gcd(a,b) = ε. [duplicate]

I know the definition of the group is associative, inverse and identity. But, I have no idea where to start and how to solve it!
1
vote
1answer
47 views

Solve $276 x\equiv 90\pmod {666}$

Solve $276 x\equiv 90\pmod {666}$ I found using Euclidean algorithm that $\gcd (276,666)=6$ then I divided by $6$ and I got: $$46x\equiv 15\pmod {111}$$ and I found that $\gcd(46,111)=1$ ...
3
votes
3answers
49 views

Two real numbers, $x$ and $y$, satisfy the condition $x + y = 2 $. Show $xy(x^2+y^2) \leq 2$

Question: Two real numbers, $x$ and $y$, satisfy the condition $x + y = 2 $. Show $xy(x^2+y^2) \leq 2$ What I have attempted: Consider $$x+y=2$$ $$ \Leftrightarrow (x+y)^2 = 2^2 ...
-3
votes
1answer
58 views

Is 10 is a Natural Number?

I was wondering that $10$ is a Natural number or not as it contains $0$ (zero) in it which is not a Natural number for sure, so $10$ is a Natural number or not ?
1
vote
1answer
45 views

Proof of the infinitude of primes using Mersenne numbers

I saw this proof in "Proofs from The Book" by Aigner and Ziegler. The proof is starts with supposing that primes, $\mathbb{P}$, is finite. Pick the greates prime number $p$. Consider the Mersenne ...
1
vote
1answer
42 views

How do we prove this claim result $2^n\cdot{T_1}\cdot{T_3}\cdot{T_5}\cdots{T_{2n-1}}=(2n)!$?

Triangle numbers $T_{n}=\frac{n(n+1)}{2}$ $T_{2n}:=3, 10, 21, 36, 55, 78, ...$ I noticed the following patterns $2\cdot3=3!$ $2^2\cdot3\cdot10=5!$ $2^3\cdot3\cdot10\cdot21=7!$ And so on... The ...
0
votes
0answers
33 views

Order of an element in $(\mathbb{Z}/n\mathbb{Z})^\times$

I am given a question to calculate the order of all the elements in $(\mathbb{Z}/13\mathbb{Z})^\times.$ I know that if a primitive root of $n$ exists (call it $g$) and if $a\in\mathbb{Z}$ such that ...
1
vote
0answers
47 views

Showing the infinitude of primes using the natural logarithm

I came across this proof in Proofs From the Book by Aigner and Ziegler. It uses the inequality $logx \leq \pi(x)+1$. (Here, we use natural logarithm) The proof starts with the inequality $log$ $x ...
1
vote
1answer
30 views

Linear system of equations over $\mathbb{Z}_7$

I had the following set of simultaneous equations in $\mathbb{Z}_7$. $$3x+5y=1$$ $$4x-5y=5$$ Now adding them we get $$7x=6$$ And this has no integer solution in $x$ since $7$ and $6$ are ...
0
votes
1answer
46 views

Is there a simple way of computing when $a^n=b^m$

I don't want exact equality just close enough to be useful in approximation. i.e. $2^{10 }= 10^3$ is very useful and used daily for an approximation. Is there a do this efficiently? Is there a way ...
0
votes
0answers
13 views

primitive root modulo prime powers [duplicate]

Suppose that $g$ is a primitive root modulo $p$. Show that, modulo $p^h$ for $h\geq 2$, every primitive root has the form $g'=g+np$ for a certain integer $n$. The proof of the previous statement ...
2
votes
0answers
36 views

Tetration of a number giving a complex number

Giving this power equation: $$S=\lim_{n\to\infty} {^n}x=-i$$ where the symbol $^nx$ means the tetration operator, we can write in a form not formally correct: $${\ ^{n}x = \ \atop {\ }} ...
-2
votes
1answer
22 views

Real polynomials from repunits to repunits ( Putnam 2007 A4) [closed]

Find all polynomials $ f$ with real coefficients such that if $ n$ is a repunit, then so is $ f(n).$
0
votes
0answers
11 views

Is this factorization of $\xi^3 \mp 1$ in $\mathbb{Z}[\omega]$ correct?

I'm trying to follow a proof of Fermat's Last Theorem for $n=3$ using the Eisenstein integers according to this paper. On page $6$ near the bottom the author gives the factorization $$\xi^3 ...
4
votes
4answers
82 views

If $p > 3$ is prime, then $12 $ divides $p^2 - 1$

First up, I know there are a lot of similar questions with 24, not 12. So bare with me please :) What is the Question? Consider the following numbers of the form $p^2 - 1$ where $p$ is prime. $$5^2 ...
0
votes
1answer
27 views

Smallest number starting with N divisble by every non zero digit of N

We are given a number N and we have to find the smallest number that starts with N and is divisble by every non zero digit of N.How can we do this ? If N is 13 then answer is 132 . According to the ...
1
vote
1answer
48 views

Not sure how to prove this statement by contradiction?

There is this a simple looking and intuitive statement but I am not sure how to start approaching this problem. Let $S=\{s_1,s_2,\ldots,s_n\}$, where $s_1,s_2,\ldots,s_n>0$ such that ...
2
votes
1answer
64 views

Is this polynomial time for greatest prime factor of odd numbers?

For natural numbers $n$ and $x,$ the number of $n^{th}$ roots that have $x$ in the whole numbers place can be represented as $(x+1)^{n}-x^{n}.$ For $p$ prime, $(x+1)^{n}-x^{n}-1\equiv0\bmod p$ iff ...
4
votes
1answer
57 views

Any more solutions to $m!!-n!=(2^k\pm1)^2$?

Factorial and double factorial $$m!!-n!=(2^k\pm1)^2$$ Where $m\ge1$ are all odd numbers $n\ge1$ are all integer numbers $k\ge0$ Is there more solution to this equation or this is the only ...
0
votes
1answer
11 views

Find all Dirichlet characters modulo $p$

In my elementary number theory class we define the following: Let $p$ be a prime, and let $\mathbb{Z}_p^*$ relatively prime residues modulo $p$. A Dirichlet character modulo $p$ is defined as a ...
19
votes
5answers
503 views

Is $11^2+12^2+13^2+14^2+15^2+16^2=1111$ special?

Is this pure coincidence or is this a special case of some well-known number-theoretic result? If the latter is true, is there some notable generalization? EDIT: Thanks to the interesting answers ...
1
vote
3answers
32 views

Find the remainder of $\sum_{i=0}^{99} 2^{i^2}$ when dividing by 7 and determine if the quotient is even or odd

I've recently had this problem in an exam and couldn't solve it. Find the remainder of the following sum when dividing by 7 and determine if the quotient is even or odd: $$\sum_{i=0}^{99} 2^{i^2}$$ ...
4
votes
1answer
61 views

Showing $n \mid \frac{x^{n}-y^{n}}{x-y}$

Let $x,y$ and $n$ be positive integers such that $n \mid (x^{n}-y^{n})$. How do I show that $\displaystyle n \mid \frac{x^{n}-y^{n}}{x-y}$. The best thing would be to show if $p^{k}\| n$, then ...
1
vote
1answer
65 views

Can composite numbers be uniquely written as a sum of two squares?

Let $X = a^2 +b^2$ where all the terms are positive integers and $X$ is a composite number and $\gcd(a,b)=1$ . Do there exist positive integers $c$ and $d$ other than $a$ and $b$ such that $X = ...
1
vote
1answer
37 views

Problem to find all $n$ in following situation [closed]

Find all $n>1$ such that $1^{n} + 2^{n} + 3^{n} +\cdots + (n-1)^{n}$ divisible by $n$. I'm not good at Number Theory so , give elementary answer.
3
votes
0answers
15 views

Is there a theory of “sums-of-squares residues”?

The theory of quadratic residues is long- and well-studied. Recall that, [somewhat simplified] if $x,a,b$ are integers, with $0 \le a < b$, such that $$x \equiv a^2\!\!\!\pmod{b},$$ then we say ...
2
votes
1answer
70 views

which odd integers $n$ divides $3^{n}+1$?

I don't understand this solution to this problem. Can anyone explain why d divides n?
0
votes
3answers
43 views

Given a range [a, b], how to find the x middle numbers?

Given a range [$a$,$b$], how can I find the $x$ middle numbers? For example: [$1$,$10$] Now I know that the middle $2$ numbers start with "$5$", but is there any way I can find the starting ...
3
votes
1answer
80 views

Is there any integer $n>1$ such that $3^n - 1$ is divisible by $2^n - 1$?

Is there any integer $n>1$ such that $3^n - 1$ is divisible by $2^n - 1$? I guess not. For every even integer $n$, we can show that $3^n - 1$ is not divisible by $2^n - 1$ because $2^n -1$ is a ...
-9
votes
1answer
80 views

Unconvincing way of showing$(-)\times(-1)=+$ [closed]

Showing why $(-)\times(-)=+$ Recalling rules of indices $b^0=1$ $\frac{b^m}{b^n}=b^{m-n}$ $b^m{\times}b^n=b^{m+n}$ We create a situation where it is involve the negatives of two numbers come face ...
1
vote
3answers
31 views

Let k $\in Z$, such that k $\ge$ -1. Then $k^2 + 1$ is not divisible by 3.

I had this on the exam a few months ago and I am doing it again just for review. I want to check if I did it right this time. Any comment would be appreciated! Proposition: Let k $\in Z$, such that ...
2
votes
1answer
33 views

Proving an identity involving floor function

Prove that : $$\left \lfloor \dfrac{2 a^2}{b} \right \rfloor - 2 \left \lfloor \dfrac{a^2}{b} \right \rfloor = \left \lfloor \dfrac{2 (a^2 \bmod b)}{b} \right \rfloor $$ Where $a$ ...