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

learn more… | top users | synonyms (1)

0
votes
0answers
14 views

Decimals of root n.

Can anybody please help me to approach the solution? I am not getting what the inequality has to do with decimals of root n.
0
votes
0answers
12 views

Proving the congruence of a Fibonacci Number

Let $F_n$ denote the $n^{th}$ fibonacci number where $F_0 = 0, F_1 = 1$. Prove that for all primes $p > 5$, $$F_p \equiv 5^{\frac{p-1}{2}} \mod (p)$$
0
votes
1answer
18 views

To find composite integers satisfying the given property.

Find all positive composite integers $n$ greater than $1$ such that for any relatively prime divisors $a$ and $b$ of $n$ with $a > 1$ and $b > 1$, the number $ab-􀀀a-􀀀b+1$ is also a divisor of ...
1
vote
3answers
59 views

Alternative Proof that $\sqrt{p}$ is Irrational when $p$ is Prime

I have found various proofs that $\sqrt{p}$ is irrational on this site, but I didn't find one similar to the one that I am about to post, so I am wondering if it is free of logical problems. Here is ...
0
votes
1answer
21 views

Ideals of $ord$

Let $p$ be a prime number in $\mathbb{Z}$. Let $R = R_p = \{x \in \mathbb{Q}\ |\ ord_p(x)\geq0\}$, which is a subring of $\mathbb{Q}$. (a) Show that the only nonzero ideals of $R$ are the ...
3
votes
0answers
19 views

Properties of the Discrete Logarithm Problem

I am self-studying Hoffstein's An Introduction to Mathematical Cryptography, and this is problem 2.3 (p. 107-08). Let $p$ be a prime and $g$ an element in $\mathbb{F}_p^*$. (a) Suppose that ...
3
votes
1answer
48 views

Why is $x^2+1$ divisible by $10$ if $x$ has a $3$ or $7$ in the one's place?

So I have the simple polynomial $x^2+1$. If I plug in ANY number that has a $3$ or a $7$ in the ones place $x^2+1$ is divisible by $10$. Why? Is there a reason for this? So numbers like ...
0
votes
2answers
49 views

Proof Verification: If $x$ is a nonnegative real number, then $\big[\sqrt{[x]}\big] = \big[\sqrt{x}\big]$

Let $x$ be a nonnegative real number and denote $[x]$ as the greatest integer less than or equal to $x$. We will attempt to prove that $\big[\sqrt{x}\big] = \big[\sqrt{[x]}\big]$. First suppose that ...
-1
votes
0answers
33 views

Hypothetical proof of Goldbach's conjecture? [on hold]

Goldbach's conjecture: Every even number greater than 4 is the sum of two prime numbers. An equivalent statement is; For all $n\geq 2$ there exists a number $e(n)$ such that $n-e(n)$ and ...
3
votes
0answers
30 views

Primes and irreducibles of $\{a+b\sqrt{-2}\ |\ a,b \in \mathbb{Z}\}$

Let $R = \{a+b\sqrt{-2}\ |\ a,b \in \mathbb{Z}\}$ Rational primes $p \geq 3$ of the form $p = a^2 + 2b^2$ factorize in $R$ as a >product of two irreducibles which are not associate. Such ...
0
votes
0answers
16 views

Is there a proof that $(n-2x)! \times n^{2x-1} > n!$ (where $x$ is a function related to the prime counting function

Is it possible to prove the following? Let $\pi$ be the prime counting function and $A(n)=\pi(2n)-\pi(n)$ $(n-2A(n))! \times n^{2A(n)-1} > n!$
3
votes
2answers
59 views

Prime counting function; when is it true that $\pi(n) > \pi(2n) -\pi(n)$?

Let $\pi$ be the prime counting function. Under what conditions is it proven true that $\pi(n) > \pi(2n) -\pi(n)$, if at all?
2
votes
1answer
17 views

How do you calculate the width of the Poset Lattice of Divisors?

Let $n = 10800 = 2^43^35^2$ I can find a set of eleven divisors of $n$ such that none divides another: $$\begin{array}{ccccc} & & & 2 3^3 & 3^35\\ & & 2^23^2 & ...
3
votes
2answers
32 views

Proof Verification: Show that $\Big[\frac{x+n}{m}\Big] = \bigg[\frac{[x]+n}{m}\bigg]$

Let $m,n \in \mathbb{Z}$ and let $x \in \mathbb{R}$. Let $[x]$ denote the floor function. We will attempt to prove $$\Big[\frac{x+n}{m}\Big] = \bigg[\frac{[x]+n}{m}\bigg]$$ Suppose without loss of ...
0
votes
2answers
37 views

How to check if a a relatively small number is prime (4 digits at most)?

I have an undergrad degree. Either I missed it or they didn't teach us, but how can I check (without using a computer) if a number, say 1033, is prime?
0
votes
2answers
49 views

Prove that for any integer $n$, if $b^2$ divides $n$, then $b$ divides $n$.

Prove that for any integer $n$, if $b^2$ divides $n$, then $b$ divides $n$. Trying to figure out this proof. The proof I'm looking at is written as $n$ = any integer, if $25|n \implies 5|n$. ...
1
vote
4answers
34 views

How do I prove that if $2\nmid n$ then $2|(n+1)$?

I'd like to prove a very simple fact, but it's stumping me: namely, that if $2 \nmid n$ then $2\mid(n+1)$. How would this usually be done?
1
vote
3answers
38 views

negative one times positive one is negative one

This is a question I was surprised that no one on this forum has asked(as far as my search went). I gave a proof that negative times negative = positive. But it relied on the assumption negative times ...
0
votes
0answers
29 views

PID and irreducibles

Let $p$ be a prime number in $\mathbb{Z}$. Let $R = R_p = \{x \in \mathbb{Q}\ |\ ord_p(x)\geq0\}$, which is a subring of $\mathbb{Q}$. (c) Show that the only nonzero ideals of $R$ are ...
0
votes
0answers
16 views

Odd perfect numbers and $\sum_{\substack{D\mid 2n,D<\sqrt{2n}}}(D+\frac{2n}{D})$

It is known that if $m>1$ isn't a perfect square integer (isn't a square number) then the sum of divisor function can be written as $$\sigma(m)=\sum_{\substack{d\mid ...
0
votes
3answers
54 views

What is the difference between 10% and $\frac{1}{10}$

In a national competition , ech school had to choose 10% of students who participated in the competition . So my question is , why they didn't asked for $\frac{1}{10}$ of students who participated ? ...
4
votes
2answers
49 views

Roots of $x^p + x + [\alpha]_p \in \mathbb{Z}_p[x]$

Let $$g(x) = x^p + x + [\alpha]_p \in \mathbb{Z}_p[x],$$ where $p$ is prime. For which $\alpha, p \in \mathbb{Z}$ does $g(x)$ have at least one root? And for which $\alpha, p \in \mathbb{Z}$ ...
2
votes
0answers
55 views

Counting integers from $1$ to $n$ with an odd number of divisors in {1,2,3,…,k}

Question Given $n,k$ find the number of integers between $1$ and $n$ that have odd number of divisors in {1,2,3,...,k} Example If $n=10$ and $k=3$, the numbers $1(1),5(1),6(1,2,3),7(1)$ have odd ...
0
votes
1answer
12 views

In $\mathbb{Z}_{79}$, $(\alpha\gamma + 66\beta\delta, \alpha\delta + 6\beta\gamma) = (0,0) \implies (\gamma, \delta) = (0,0)$ [on hold]

How does one prove that, in $\mathbb{Z}_{79}$, if $(\alpha, \beta) \neq (0,0)$, then $$(\alpha\gamma + 66\beta\delta, \alpha\delta + 6\beta\gamma) = (0,0) \implies (\gamma, \delta) = (0,0).$$ This ...
2
votes
2answers
32 views

Is there an alternative approach to the definition of prime numbers based on the definition of the natural logarithm?

Is there an alternative approach to the definition of prime numbers based on the definition of the natural logarithm? These are my thoughts about it, the questions are at the end: Basically when a ...
3
votes
0answers
35 views

Converse of Fermat's Little Theorem.

If $a^n\equiv a \pmod n$ for all integers $a$, does this imply that $n$ is prime? I believe this is the converse of Fermat's little theorem.
0
votes
1answer
27 views

Smallest $n$ such that $U(n)$ contains a subgroup isomorphic to $\mathbb Z_5 \oplus \mathbb Z_5$

I solved the following exercise: Find an integer $n$ such that $U(n)$ contains a subgroup isomorphic to $\mathbb Z_5 \oplus \mathbb Z_5$. Here $U(n)$ is the group of units modulo $n$. To solve it ...
1
vote
0answers
9 views

On the existence of magic squares of every order different from $2$

I was reading about magic squares and suppose that we speak here only of the magic squares that have in itself numbers from $1$ to $n^2$. It is easy to see that we cannot have $2$x$2$ magic square ...
3
votes
1answer
41 views

In $U(55)$ show $x \mapsto x^3$ is injective

I am stuck on showing that $\varphi : U(55) \to U(55) $ given by $x \mapsto x^3$ is an isomorphism. I already knwo that $\psi: U(n)\to U(n), \psi(x) = x^k$ is an isomorphism if and only if $\gcd(k,n) ...
1
vote
2answers
35 views

I don't understand a step in the proof of Euler's Theorem, please explain

I am trying to learn the proof for Euler's theorem which states: If $\gcd(a,m)=1$ then $a^{\phi(m)} \equiv 1 \mod m$. The proof goes like this. Take the reduced residue system modulo $m$. ...
1
vote
3answers
58 views

For which $n \in \mathbb{N}$ does $x^8 + [2]_nx^7+[6]_nx^6-x^2-[2]_nx - [6]_n = [0]_n$ have at least $7$ distinct solutions?

I have to find one $n \in \mathbb{N}$ such that $$x^8 + [2]_nx^7+[6]_nx^6-x^2-[2]_nx - [6]_n = [0]_n$$ has at least $7$ distinct solutions in $\mathbb{Z}_n$ (or, equivalently, $f(x) = x^8 + ...
5
votes
1answer
43 views

How to prove this curiosity that has to do with cubes of certain numbers?

I saw on facebook some image on which these identities that I am going to write below are labeled as "amazing math fact" and on the image there are these identities: $1^3+5^3+3^3=153$ ...
1
vote
1answer
43 views

Find all $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime

I'll try to format my question in a manner such that you can skip (irrelevant) parts. Exercise: Find all natural $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime. Motivation: I'm trying to ...
0
votes
0answers
38 views

How to square a number that got more digits than search results “digits” on Google.

I am implementing the quadratic sieve algorithm. And I got run in unexpected problem. Take a look at those two final steps of the algorithm as described in wiki. Use linear algebra to find a ...
1
vote
1answer
15 views

Sums of remainders in Euclidean GCD algorithm

I've noticed that when going through the steps of Euclidean GCD algorithms, very often the sum of the remainders in the steps $s_{i+1}$ and $s_{i+2}$ will be equal to the remainder in step $s_i$. ...
-1
votes
0answers
42 views

Find $a,b,c \in \{1,2,..,9\}$ such that $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{10+a}{10+b}$ [on hold]

Find $a,b,c \in \{1,2,..,9\}$ such that $$\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{10+a}{10+b}.$$ It seems to be easy but I want a smart solution.
1
vote
2answers
28 views

When the Sum of digits exceed the Number of Divisors

Could somebody help me prove that there are a infinite number of natural numbers for which their sum of digits exceeds the number of divisors? If $S(n)$ denoted the sum of digits, and $\sigma_k(n)$ ...
1
vote
2answers
49 views

$x^4 - y^4 = 2z^2$ intermediate step in proof

I am ultimately trying to prove, for an Exercise in Burton's Elementary Number Theory, that $x^4 - y^4 = 2z^2$ has no solution in the positive integers. I can establish that if there is a solution, ...
2
votes
1answer
52 views

Gaussian elimination algorithm performance

I am developing the quadratic sieve algorithm and I reached a new bottle neck: The matrix processing. I been reading quit a lot about this topic and I found many solutions Gaussian elimination: ...
-1
votes
1answer
41 views

Linear Combinations? [on hold]

Suppose $a$ is an integer such that $a$ divides $a_j$ for all $1 \le j \le n$. Show that $a$ divides any integer linear combination of $a_1, a_2, \ldots, a_n$.
0
votes
1answer
24 views

Prove that if $\gcd (a,n)=1$, $as=1 \pmod n$ has a solution

I can prove that if $\gcd (a,n)=1$, then $as=1 \pmod{n}$ has a solution. However, I cannot prove that the solution $s$ is in the set $\{1, 2, ..., n-1\}$.
-1
votes
1answer
53 views

Prove that $3|n ^{2} -1$ [on hold]

If $n$ is an integer such that $n\ge2$ and $3|n-1$, show that $3|n^{2}-1$.
-3
votes
0answers
47 views

Find the positive integers $\overline {abc}$ such that $\frac{1}{a} +\frac{1}{b}+\frac{1}{c}$=$\frac{\overline {1b}}{\overline {1a}}$ [on hold]

Find the positive integers $\overline {abc}$ such that $$\frac{1}{a} +\frac{1}{b}+\frac{1}{c}=\frac{\overline {1b}}{\overline {1a}}.$$ Can you help me with a solution without to consider the case ...
1
vote
0answers
19 views

Stern-Brocot Tree and sum of coefficients of continued fraction

Suppose we are given a continued fraction $$\frac{p}{q}=a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}+\frac{1}{a_{4}+\cdots}}}$$ I am trying to find an expression, possibly asymptotic, for the sum of the ...
2
votes
2answers
43 views

Given integers $x,\,y$ s.t. $x^2-16=y^3$, show that $x+4$ and $x-4$ are perfect cubes

Suppose $x$ and $y$ are some integers satisfying $$x^2-16=y^3.$$ I'm trying to show that $x+4$ and $x-4$ are both perfect cubes. I know that the greatest common divisor of $x+4$ and $x-4$ must divide ...
1
vote
0answers
21 views

What are the biggest possible number of equal values on this NxN box?

In a nXn box(n>3),a number is written on every cell such that the sums along all rows and columns are the same.Not all numbers are the same.What is the biggest possible number of equal values in the ...
0
votes
1answer
10 views

If $N = {q^k}{n^2}$ is an odd perfect number given in Eulerian form, does $\sigma(n^2)/q$ divide $2n^2 - \sigma(n^2)$?

Let $\sigma(x)$ be the sum of the divisors of $x$. A number $X$ is called perfect if $\sigma(X) = 2X$. Denote the abundancy index $\sigma(X)/X$ by $I(X)$. If $N$ is odd and perfect, then $N$ can be ...
2
votes
1answer
29 views

Integer (or whole) numbers in arbitrary fields.

Given an arbitrary field $K$, may I define an integer in $K$? I have found how to define an algebraic number in $K$ and how to define an integer algebraic number in $K$. For instance, let ...
0
votes
0answers
25 views

Can you show a proof of Unique Factorization of Integers Theorem (Fundamental Theorem of Arithmetic)?

I understand the proof of "Any integer greater than 1 is divisible by a prime number" by strong mathematical induction. But I don't understand why Unique Factorization of Integers Theorem follows ...
2
votes
1answer
62 views

Find $\sum_{i=1}^{2000}\gcd(i,2000)\cos\left(\frac{2\pi\ i}{2000}\right)$

What is the value of the following sum? $$\sum_{i=1}^{2000}\gcd(i,2000)\cos\left(\frac{2\pi\ i}{2000}\right)$$ where $\gcd$ is the greatest common divisor.