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

learn more… | top users | synonyms (1)

3
votes
4answers
53 views

Sum of Digit Permutations

The question simply states "Let a secret three digit number be $cba$. If the sum of $cab + bac + bca + abc + acb = 2536$, what is $cba$?" I have no idea how to approach this problem. Any hints or help ...
2
votes
1answer
27 views

Unknown random number generator

I recently browsed through someone else's code and found a section where a pseudo random number generator is implemented. I know that random number generation is not an easy task, some even regard as ...
9
votes
1answer
68 views

Is there any polynomial function $f$ such that If $\gcd(p,q)=1$ then $\gcd(f(p),f(q))=1$ for all such $p,q$?

Is there a polynomial, $f(x)$, such that for all natural numbers $p$ and $q$, if $\gcd(p, q) = 1$ then $\gcd(f(p), f(q)) = 1$? Note : Function $f(x)$ must be a polynomial in $x$, not depend on $p$ or ...
2
votes
1answer
65 views

Why do the closest primes whose distance $d \gt 1$ to $c(n)=\frac{(n+1)!+n!}{2}$ have always $d \in \Bbb P$?

I have made the following observation: define the center of $n!$ and $(n+1)!$, $c(n)$, as the number located exactly in the middle of $(n+1)!$ and $n!$. Def: $\forall n \gt 2\ , \ ...
0
votes
0answers
4 views

Linear Diophantine Equations with restrictions on coefficients

Given $x, y, a, b, c\in \mathbb{Z^+}$ where $a<b<c$, are there any known results which might help me put bounds on $x$ and $y$ in the equations $ax+by=2c$ and $ax+c=2b$? Thanks in advance.
0
votes
1answer
59 views

number of elements of the form $2^k$, $k\in\mathbb{N}$?

Let $n\in\mathbb{N}$, and consider the set $H:=\{1,2,\cdots, 3n\}$. How many elements of $H$ are of the form $2^k$, with $k\in\mathbb{N}$? I think that there are two cases to consider, namely: $n$ odd ...
-1
votes
1answer
42 views

product free, property P

In jurnal mocow jurnal combinatorik and number theory "multiplicative property of set residue say in paragraph one, say for every positive integer, every set of residues mod of cardinality larger than ...
2
votes
2answers
45 views

If $a\mid b+c$ and $\gcd(b,c)=1$, prove $\gcd(a,b)=\gcd(a,c)=1$

I have the following: $b+c=av$ for some integer $v$, and $a=dm$ and $b=dn$ for $d=\gcd(a,b)$ and some integers $m,n$. Then, $c=av-b=dmv-dn=d(mv-n)$. So, $d|c$, and we know that $d|a$ and $d|b$. I ...
2
votes
1answer
150 views

Proof of $6174$ as the unique 4-digit Kaprekar's constant

I'm studying number theory and I meet this question: (For those who knows Kaprekar's constant may skip 1st paragraph.) Let $a$ be an integer with a 4-digit decimal expansion, with not all ...
2
votes
1answer
47 views

Is equivalent this expression to Wilson's theorem?

According to Wilson's theorem, $n$ is prime if and only if (1): $$(n-1)! \equiv -1 \pmod{n}$$ Would the following expression be valid and equivalent? (2) ...
3
votes
2answers
39 views

Under what $p$, $-1$ is a square in $\mathbf F_p$? [duplicate]

Let $p$ be a prime number. If -1 is a square in $\mathbf F_p$, it means that there exists an element of order 4. So $p-1$ is divisible by 4 and therefore $p \equiv 1$ (mod 4). I wonder the converse is ...
0
votes
0answers
23 views

Show that $\sum_{d \mid p-1} T(d) = p-1$ where $p$ is prime and $T(d) = \# \{a \mid 1 \le a \le p - 1, \, (a,\,p-1)=d \}$.

I'm trying to show that $$\sum_{d \mid p-1} T(d) = p-1,$$ where $p$ is prime and $T(d) = \# \{a \mid 1 \le a \le p - 1, \, (a,\,p-1)=d \}$. I really don't even know how to begin on this problem. A ...
2
votes
1answer
75 views

Theorem about prime numbers which are one more than a multiple of $8$

Assume the following: A prime $p>2$ can be written as $p=m^2+n^2$ for integral $m,n$ iff $p$ is $1$ more than a multiple of $4$. Now, prove that every prime which is one more than a multiple of ...
1
vote
1answer
41 views

How to calculate the gcd of two polynomials $\mod 7$

I need to find gcd of $x^4-3x^3-2x+6$ and $x^3-5x^2+6x+7$ in $\mathbb Z/7 \mathbb Z[x]$, the integer polynomials mod $7$. Please any help will be appreciated.
-1
votes
0answers
24 views

Arithmetic progressions in elementary number theory

D.Burton gives the following exercise: If $p$ is a prime and $p$ does not divide $b$, a) prove that in the arithmetic progression: $$1)\quad a,a+b,a+2b,a+3b,...$$ every $p$th is divisible by $p$. b) ...
0
votes
1answer
20 views

find the prime factorization of $x^3-5x^2+6x+7$ in $Z/11Z$

I need to find the prime factorization of $f = x^3-5x^2+6x+7$ in $Z/11Z$ I tried the following but not sure if it is correct and if there is a better and faster way to do it. first i tried one by ...
1
vote
1answer
28 views

Can I use the fact that $\mathbb{N}$ is a total order to prove that it is infinite?

We can show the canonical ordering $\le$ gives a total ordering on $\mathbb{N}$. We can show that any finite subset of a totally-ordered set has a maximal/greatest element. For brevity, take these ...
1
vote
0answers
38 views

For which prime numbers $p$ there exist $x,y\in \Bbb{Z}$ such that $p=x^2+2y^2$? [duplicate]

For which prime numbers $p$ there exists $x,y\in \Bbb{Z}$ such that $p=x^2+2y^2$? I guess I am to use continued fraction, but I am not sure how. I know how to find solutions for defined numbers but I ...
1
vote
2answers
60 views

if three integer such diophantine equation How find $x+y+z$

following Diophantine equation $$xy^2+yz^2+zx^2=x^2y+y^2z+z^2x+x+y+z$$ ie:$(x-y)(y-z)(z-x)=x+y+z$ where $x,y,z$ are integers. can find $x+y+z$ I tried some values and got some near ...
0
votes
1answer
43 views

prove that for each $n \in\mathbb N$ odd, $\phi(n) \ne 2^{32}$

I need to prove that for each $n \in\mathbb N$ odd, $$\phi(n) \ne 2^{32}.$$ What I tried: I assumed that $\phi(n)$ is indeed a power of 2 then, because of this assumption I know that $ n = p_1 ...
3
votes
2answers
53 views

prove that there are infinitely many numbers of the form $x = 111…1$ such that $31|x$

I need to prove that there are infinitely many numbers of the form $x = 111....1$ such that $31|x$ what i tried - I wrote x as $\sum_0^{n-1} 10^i$ i know that $(10,31) = 1 $ now im stuck .. any ...
1
vote
2answers
50 views

Show that $10^{n(p-1)}\equiv 1\pmod{\! 9p}$ for $p\ge 7$

I need to prove that for each prime $p \ge 7$ and for each $n \in\Bbb N$ $$10^{n(p-1)} \equiv 1 \pmod {9p}$$ What I've tried: I know $10$ is coprime to $9$ and $p$, so it is coprime to $9p$. I ...
1
vote
2answers
25 views

Find minimal $x\in\Bbb N$ that solves the linear congruence

I need to find minimal $x\in\Bbb N$ that solves the linear congruences: $6x \equiv 2 \pmod {\!4}$ $3x \equiv 6 \pmod {\!9}$ $x \equiv 15 \pmod {\! 17}$ I divided the first congruence by $2$ and ...
3
votes
0answers
47 views

Find naturals that are sum of numbers with the same digits in inverse order

In a test I've found the following exercise: We say $n \in \mathbb{N}$ is reflexive if is the sum of two naturals $x$ and $y$ such that $y$ has the same digits of $x$ witten in the inverse order ...
2
votes
1answer
34 views

Computing periodic continued fractions.

Compute $[1,2,3,\overline{1,4}]$ where $\overline{1,4}$ is the periodic part. I looked into explanations about that, but haven't come by an actual algorithm of computing such a thing. I know it is ...
2
votes
5answers
170 views

$x^2-y^2=196$, can we find the value of $x^2+y^2$?

$x$ and $y$ are positive integers. If $x^2-y^2=196$, can we know what the value of $x^2+y^2$ is? Can anyone explain this to me? Thanks in advance.
3
votes
1answer
100 views

A real number is rational $\iff$ its continued fraction expansion is finite.

I know that if this expansion is finite, then I can go to the lowest denominator in the whole fraction and turn it into a fraction and keep doing so until I get a fraction which means the number is ...
3
votes
1answer
54 views

Encyclopedia of Mathematical Proofs with no English

I was wondering if anyone is aware of a modern book that builds a subset of elementary number theory from Peano axioms preferably in a Principia Mathematica fashion? Or similarly an encyclopedia of ...
10
votes
6answers
248 views

Determine whether $\frac{1000!}{100!^{10}}$ is an integer

Can you give an idea, how to find out whether the result of ${1000!}/{100!^{10}}$ an integer. Modulo division? But what I met was about powers like $2^{100}/125$...
2
votes
1answer
21 views

Find all the natural numbers which are coprimes to $n$ and are not a fermat witness to compositeness of $n$.

The number $n=35$ is given. Find all the natural numbers $1 \leq a \leq n-1$ which are coprimes to $n$ and are not a fermat witness to compositeness of $n$. Is it enough to say that we are looking ...
1
vote
1answer
23 views

Can we construct a successor function from successive applications of those two functions?

Let $f(x) = 5 \cdot x + 3$ and $g(x) = \frac{x}{8}$, Is it possible to construct a function $s$ such that $s(x) = x + 1$ via successive applications of any of f and g?
0
votes
4answers
62 views

Prove by induction that sum of an odd number of odd numbers is odd

Prove by induction that if $n$ is odd and $a_1,\,\cdots,\,a_n$ are odd, then $\begin{aligned}\sum_{i = 1}^n a_i\end{aligned}$ is odd. Progress: If $n = 1$ then $\sum_{i = 1}^1 a_i = a_1$, so the ...
0
votes
2answers
41 views

How to find the coefficients of Bezout's lemma?

Please explain me how to compute the coefficients of Bezout's lemma with the help of an example. Also, if I develop an algorithm to find all prime numbers which performs one operation to find ...
0
votes
1answer
62 views

Is this the general equation of FLT that generates Pythagorean-triples? [closed]

Let us try to derive the General equation of FLT for all powers as under: If ac , ...
0
votes
0answers
49 views

How can we find the private key?

Alice uses the ElGamal signature scheme with the variables $p=47$, $q=23$ and $g=2$. For two different messages $m_1, m_2$ with $h(m_1)=4, h(m_2)=3$ she produces the signatures $(r_1, s_1)=(14, 8)$ ...
0
votes
2answers
103 views

When will $ax+1$ be divisible by $b$?

Consider two natural numbers $a$ and $b$ such that $b$ is prime and $a$ is indivisible by $b$. Then, for which integral values of $x$ should $ax+1$ be divisible by $b$ ? I tried different values of ...
4
votes
1answer
61 views

Why are there not primality tests based on comparing the candidate $n$ with values of some $k \in [0,n]?$

I am learning basic number theory and as far as I could read, basically all the primality tests (or proven primality theorems) that are able to decide if a given $n$ is prime (or a special ...
4
votes
1answer
69 views

Non existence of absolute euler pseudoprimes

A natural number $n$ is called an Euler pseudoprime(sometimes Euler-Jacobi pseudoprime) wrt to $a$ iff $$a^{(\frac{n-1}2)} \equiv \Big(\frac an\Big) \pmod n$$ where $\Big(\frac an\Big)$ is the ...
0
votes
1answer
29 views

Question about inequalities between consecutive primes

Can any two consecutive primes $p_n$ and $p_{n+1}$ satisfy the inequality $3p_n+1<2p_{n+1}$
0
votes
3answers
41 views

How to get all natural numbers out of all odd numbers

I'm building a program that does something if a counter is odd, and something else if it is even. For the odd part of the program, I get all odd natural numbers (one at a time) so $1, 3, 5, 7... $ ...
0
votes
2answers
37 views

Arithmetic sequence of exponentials

There is an arithmetic sequence $2^a, 3^b, 4^c$ such that a,b and c are positive integers. The question posed is to find ALL possible ordered triplets $(a,b,c)$. The constant difference d between ...
0
votes
0answers
18 views

Question about the sums of the entries in an infinite array

Imagine you have an infinite array of numbers. You can divide this array in columns with labels of opposite signs that go to infinity and negative infinity starting from the center of the array. Each ...
4
votes
1answer
45 views

Prime - composite numbers

Let $n>2$ a natural number. We define the following sets: $$S=\{1 \leq a \leq n : (a,n)=1, a^{n-1} \not\equiv 1\pmod n\} \\ T=\{1 \leq b \leq n : (b,n)=1, b^{n-1} \equiv 1 \pmod n\}$$ Are there ...
3
votes
0answers
43 views

Set of integers bounded above

Could you please check the validity of my solution to the following question? Example: Show that if a set $A$ of integers is bounded above, then $A$ has a largest element. My attempt is as ...
1
vote
3answers
53 views

How can we find $m_2$ such that $m \equiv m_1 m_2 \pmod n$ ?

Let $m, m_1 \in (\mathbb{Z}/n\mathbb{Z})^{\times}$. How can we find $m_2$ such that $m \equiv m_1 m_2 \pmod n$ ?? Coud you give me some hints??
6
votes
2answers
125 views

Is $y^2=x^3+7$ unsolvable modulo some $n$?

The equation $y^2=4x^3+7$ has no integral solution since $y^2\equiv4x^3+7\pmod4$ has no solution (i.e. has no solution in $\Bbb{Z}/4\Bbb{Z}$). It is well known that $y^2=x^3+7$ has no integral ...
1
vote
3answers
63 views

Even and odd proof - if n is even then $n^{2} -1$ is odd. [closed]

How can I prove that if $n$ is even then $n^2 -1$ is odd?
3
votes
1answer
109 views

When is $c^4-72b^2c^2+320b^3c-432b^4$ a positive square?

In trying to solve a certain [third-degree] Diophantine equation, I have used the quadratic equation to determine that $$c^4-72b^2c^2+320b^3c-432b^4$$ must be a positive integer square, where $c$ and ...
0
votes
1answer
18 views

prove or disprove - $p(x)$ = $\sum_0^n$ $a_iX^i$ $c,d,a_i \in $ Z , $n \in N$ then c-d|p(c)-p(d)

Prove or disprove that if $p(x)$ = $\sum \limits _{i=0} ^n a_i X^i$ with $a_i \in \Bbb Z$ and if $c, d \in \Bbb Z$, then $ c-d \space | \space p(c)-p(d)$. What I tried: I know both sums can start ...
0
votes
5answers
102 views

Find $7^{999,999}$ modulo (10)

I am trying to find $7^{999,999}$ modulo (10) using Euler's Theorem: If $m \in \mathbb{Z^+}, a \in \mathbb{Z}, (a,m) = 1$ then $a^{\phi(m)} \equiv 1$ (mod m). I am unsure though how to use it ...