Name for this Algorithm
$begingroup$
I've managed to prove a bunch of properties about this algorithm that I came up with. I'm now curious to know it's name to see what other people have done.
Given a number in base b $$N_0 = b N_X + N_L, qquad 0 leq N_L leq b-1 $$
And a divisor also in base b $$D = b D_X + D_L, qquad 0 leq D_L leq b-1 $$
($N_L$ and $D_L$ are the last digits of N and D)
Then compute $$N_{i+1} = left| begin{matrix} N_X & N_L \ D_X & D_L end{matrix} right|$$
I've shown this algorithm to a few lecturers at my uni and they don't know a name for it but suspect it is some sort of variation on the Euclidean Algorithm.
It can be used for divisibility tests (especially good in binary, if $D_L = 1$, or if $D$ is prime )
E.g. Does $9734$ divide by $31$
$N_X = 973$, $N_L = 4$
$D_X=3$, $D_L = 1$
$$N_0 = 9734$$
$$N_1 = left| begin{matrix} 973 & 4 \ 3 & 1 end{matrix} right| = 961$$
$$N_2 = left| begin{matrix} 96 & 1 \ 3 & 1 end{matrix} right| = 93$$
$$N_3 = left| begin{matrix} 9 & 3 \ 3 & 1 end{matrix} right| = 0$$
If the algorithm hits $0$, then $D|N$ (Under certain conditions, counter example N=48, D=36)
Also, if $D_L = 1$ the quotient appears
$$N_1 = left| begin{matrix} 973 & color{red}{4} \ 3 & 1 end{matrix} right| = 961$$
$$N_2 = left| begin{matrix} 96 & color{red}{1} \ 3 & 1 end{matrix} right| = 93$$
$$N_3 = left| begin{matrix} 9 & color{red}{3} \ 3 & 1 end{matrix} right| = 0$$
$9734 = color{red}{314} times 31$
Any help is greatly appreciated! Thanks, Ben
algorithms divisibility euclidean-algorithm
$endgroup$
add a comment |
$begingroup$
I've managed to prove a bunch of properties about this algorithm that I came up with. I'm now curious to know it's name to see what other people have done.
Given a number in base b $$N_0 = b N_X + N_L, qquad 0 leq N_L leq b-1 $$
And a divisor also in base b $$D = b D_X + D_L, qquad 0 leq D_L leq b-1 $$
($N_L$ and $D_L$ are the last digits of N and D)
Then compute $$N_{i+1} = left| begin{matrix} N_X & N_L \ D_X & D_L end{matrix} right|$$
I've shown this algorithm to a few lecturers at my uni and they don't know a name for it but suspect it is some sort of variation on the Euclidean Algorithm.
It can be used for divisibility tests (especially good in binary, if $D_L = 1$, or if $D$ is prime )
E.g. Does $9734$ divide by $31$
$N_X = 973$, $N_L = 4$
$D_X=3$, $D_L = 1$
$$N_0 = 9734$$
$$N_1 = left| begin{matrix} 973 & 4 \ 3 & 1 end{matrix} right| = 961$$
$$N_2 = left| begin{matrix} 96 & 1 \ 3 & 1 end{matrix} right| = 93$$
$$N_3 = left| begin{matrix} 9 & 3 \ 3 & 1 end{matrix} right| = 0$$
If the algorithm hits $0$, then $D|N$ (Under certain conditions, counter example N=48, D=36)
Also, if $D_L = 1$ the quotient appears
$$N_1 = left| begin{matrix} 973 & color{red}{4} \ 3 & 1 end{matrix} right| = 961$$
$$N_2 = left| begin{matrix} 96 & color{red}{1} \ 3 & 1 end{matrix} right| = 93$$
$$N_3 = left| begin{matrix} 9 & color{red}{3} \ 3 & 1 end{matrix} right| = 0$$
$9734 = color{red}{314} times 31$
Any help is greatly appreciated! Thanks, Ben
algorithms divisibility euclidean-algorithm
$endgroup$
add a comment |
$begingroup$
I've managed to prove a bunch of properties about this algorithm that I came up with. I'm now curious to know it's name to see what other people have done.
Given a number in base b $$N_0 = b N_X + N_L, qquad 0 leq N_L leq b-1 $$
And a divisor also in base b $$D = b D_X + D_L, qquad 0 leq D_L leq b-1 $$
($N_L$ and $D_L$ are the last digits of N and D)
Then compute $$N_{i+1} = left| begin{matrix} N_X & N_L \ D_X & D_L end{matrix} right|$$
I've shown this algorithm to a few lecturers at my uni and they don't know a name for it but suspect it is some sort of variation on the Euclidean Algorithm.
It can be used for divisibility tests (especially good in binary, if $D_L = 1$, or if $D$ is prime )
E.g. Does $9734$ divide by $31$
$N_X = 973$, $N_L = 4$
$D_X=3$, $D_L = 1$
$$N_0 = 9734$$
$$N_1 = left| begin{matrix} 973 & 4 \ 3 & 1 end{matrix} right| = 961$$
$$N_2 = left| begin{matrix} 96 & 1 \ 3 & 1 end{matrix} right| = 93$$
$$N_3 = left| begin{matrix} 9 & 3 \ 3 & 1 end{matrix} right| = 0$$
If the algorithm hits $0$, then $D|N$ (Under certain conditions, counter example N=48, D=36)
Also, if $D_L = 1$ the quotient appears
$$N_1 = left| begin{matrix} 973 & color{red}{4} \ 3 & 1 end{matrix} right| = 961$$
$$N_2 = left| begin{matrix} 96 & color{red}{1} \ 3 & 1 end{matrix} right| = 93$$
$$N_3 = left| begin{matrix} 9 & color{red}{3} \ 3 & 1 end{matrix} right| = 0$$
$9734 = color{red}{314} times 31$
Any help is greatly appreciated! Thanks, Ben
algorithms divisibility euclidean-algorithm
$endgroup$
I've managed to prove a bunch of properties about this algorithm that I came up with. I'm now curious to know it's name to see what other people have done.
Given a number in base b $$N_0 = b N_X + N_L, qquad 0 leq N_L leq b-1 $$
And a divisor also in base b $$D = b D_X + D_L, qquad 0 leq D_L leq b-1 $$
($N_L$ and $D_L$ are the last digits of N and D)
Then compute $$N_{i+1} = left| begin{matrix} N_X & N_L \ D_X & D_L end{matrix} right|$$
I've shown this algorithm to a few lecturers at my uni and they don't know a name for it but suspect it is some sort of variation on the Euclidean Algorithm.
It can be used for divisibility tests (especially good in binary, if $D_L = 1$, or if $D$ is prime )
E.g. Does $9734$ divide by $31$
$N_X = 973$, $N_L = 4$
$D_X=3$, $D_L = 1$
$$N_0 = 9734$$
$$N_1 = left| begin{matrix} 973 & 4 \ 3 & 1 end{matrix} right| = 961$$
$$N_2 = left| begin{matrix} 96 & 1 \ 3 & 1 end{matrix} right| = 93$$
$$N_3 = left| begin{matrix} 9 & 3 \ 3 & 1 end{matrix} right| = 0$$
If the algorithm hits $0$, then $D|N$ (Under certain conditions, counter example N=48, D=36)
Also, if $D_L = 1$ the quotient appears
$$N_1 = left| begin{matrix} 973 & color{red}{4} \ 3 & 1 end{matrix} right| = 961$$
$$N_2 = left| begin{matrix} 96 & color{red}{1} \ 3 & 1 end{matrix} right| = 93$$
$$N_3 = left| begin{matrix} 9 & color{red}{3} \ 3 & 1 end{matrix} right| = 0$$
$9734 = color{red}{314} times 31$
Any help is greatly appreciated! Thanks, Ben
algorithms divisibility euclidean-algorithm
algorithms divisibility euclidean-algorithm
asked Jan 6 at 16:20
Ben CrossleyBen Crossley
840318
840318
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
It's the special case $m = 10c!+!d, n = 10a!+!b $ of the following
$quad bbox[5px,border:1px solid red]{(a,n) = 1,Rightarrow, (m,n) = (am!-!cn,n)} $ by $,(m,n)=(am,n) = (am!-!cn,n)$
So $ (a,b)=1,Rightarrow, (10c!+!d,10a!+!b) = (ad!-!bc,10a!+!b), $ exactly as you observed.
Remark $ $ Various well-known divisibity test rules are essentially special cases of this, e.g. the rule for divisibility by $7$ follows from the rule for $21$ given below (we negated $,ad! -! bc = 2d!-!c,$ below)
$qquadqquad qquad , (10c!+!d,10(2)!+!1) = (c!-!2d, 10(2)!+!1)$
${rm similar to your} (10c!+!d,10(3)!+!1) = (c!-!3d, 10(3)!+!1) $ rule for $,31$
$endgroup$
$begingroup$
Do you know if there is a name for it? Or how I might find other work on it? I've used it to do some cool things with Gaussian integers and I highly doubt I'm the first person to play with this idea!
$endgroup$
– Ben Crossley
Jan 7 at 23:28
$begingroup$
@Ben I'm not aware of any common name for this. Things like this are folklore, e.g. occurring in various guises in divisibility tests. In number rings analogous results are often special cases of Hermite normal form algorithms for modules and related results, e.g. see here and here. If you give more details about your Gaussian integer results then I may be able to be more specific.
$endgroup$
– Bill Dubuque
Jan 8 at 0:45
$begingroup$
@Ben By the way, another angle is to view $,m = f(10),$ as a polynomial of degree $k$ in the radix. Then $$bmod 10a!+!b!:, 10equiv -b/a,Rightarrow,(f(10),10a!+!b) = (a^kf(-b/a),10a!+!b)qquad$$ and the algorithm can be viwed as a recursive scheme for evaluating $,a^kf(-b/a),$ (a homogeneous polynomial in $,a,b),,$ analogous to Horner evaluation and related results. If this is of interest let me know and I can elaborate.
$endgroup$
– Bill Dubuque
Jan 8 at 0:46
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064058%2fname-for-this-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It's the special case $m = 10c!+!d, n = 10a!+!b $ of the following
$quad bbox[5px,border:1px solid red]{(a,n) = 1,Rightarrow, (m,n) = (am!-!cn,n)} $ by $,(m,n)=(am,n) = (am!-!cn,n)$
So $ (a,b)=1,Rightarrow, (10c!+!d,10a!+!b) = (ad!-!bc,10a!+!b), $ exactly as you observed.
Remark $ $ Various well-known divisibity test rules are essentially special cases of this, e.g. the rule for divisibility by $7$ follows from the rule for $21$ given below (we negated $,ad! -! bc = 2d!-!c,$ below)
$qquadqquad qquad , (10c!+!d,10(2)!+!1) = (c!-!2d, 10(2)!+!1)$
${rm similar to your} (10c!+!d,10(3)!+!1) = (c!-!3d, 10(3)!+!1) $ rule for $,31$
$endgroup$
$begingroup$
Do you know if there is a name for it? Or how I might find other work on it? I've used it to do some cool things with Gaussian integers and I highly doubt I'm the first person to play with this idea!
$endgroup$
– Ben Crossley
Jan 7 at 23:28
$begingroup$
@Ben I'm not aware of any common name for this. Things like this are folklore, e.g. occurring in various guises in divisibility tests. In number rings analogous results are often special cases of Hermite normal form algorithms for modules and related results, e.g. see here and here. If you give more details about your Gaussian integer results then I may be able to be more specific.
$endgroup$
– Bill Dubuque
Jan 8 at 0:45
$begingroup$
@Ben By the way, another angle is to view $,m = f(10),$ as a polynomial of degree $k$ in the radix. Then $$bmod 10a!+!b!:, 10equiv -b/a,Rightarrow,(f(10),10a!+!b) = (a^kf(-b/a),10a!+!b)qquad$$ and the algorithm can be viwed as a recursive scheme for evaluating $,a^kf(-b/a),$ (a homogeneous polynomial in $,a,b),,$ analogous to Horner evaluation and related results. If this is of interest let me know and I can elaborate.
$endgroup$
– Bill Dubuque
Jan 8 at 0:46
add a comment |
$begingroup$
It's the special case $m = 10c!+!d, n = 10a!+!b $ of the following
$quad bbox[5px,border:1px solid red]{(a,n) = 1,Rightarrow, (m,n) = (am!-!cn,n)} $ by $,(m,n)=(am,n) = (am!-!cn,n)$
So $ (a,b)=1,Rightarrow, (10c!+!d,10a!+!b) = (ad!-!bc,10a!+!b), $ exactly as you observed.
Remark $ $ Various well-known divisibity test rules are essentially special cases of this, e.g. the rule for divisibility by $7$ follows from the rule for $21$ given below (we negated $,ad! -! bc = 2d!-!c,$ below)
$qquadqquad qquad , (10c!+!d,10(2)!+!1) = (c!-!2d, 10(2)!+!1)$
${rm similar to your} (10c!+!d,10(3)!+!1) = (c!-!3d, 10(3)!+!1) $ rule for $,31$
$endgroup$
$begingroup$
Do you know if there is a name for it? Or how I might find other work on it? I've used it to do some cool things with Gaussian integers and I highly doubt I'm the first person to play with this idea!
$endgroup$
– Ben Crossley
Jan 7 at 23:28
$begingroup$
@Ben I'm not aware of any common name for this. Things like this are folklore, e.g. occurring in various guises in divisibility tests. In number rings analogous results are often special cases of Hermite normal form algorithms for modules and related results, e.g. see here and here. If you give more details about your Gaussian integer results then I may be able to be more specific.
$endgroup$
– Bill Dubuque
Jan 8 at 0:45
$begingroup$
@Ben By the way, another angle is to view $,m = f(10),$ as a polynomial of degree $k$ in the radix. Then $$bmod 10a!+!b!:, 10equiv -b/a,Rightarrow,(f(10),10a!+!b) = (a^kf(-b/a),10a!+!b)qquad$$ and the algorithm can be viwed as a recursive scheme for evaluating $,a^kf(-b/a),$ (a homogeneous polynomial in $,a,b),,$ analogous to Horner evaluation and related results. If this is of interest let me know and I can elaborate.
$endgroup$
– Bill Dubuque
Jan 8 at 0:46
add a comment |
$begingroup$
It's the special case $m = 10c!+!d, n = 10a!+!b $ of the following
$quad bbox[5px,border:1px solid red]{(a,n) = 1,Rightarrow, (m,n) = (am!-!cn,n)} $ by $,(m,n)=(am,n) = (am!-!cn,n)$
So $ (a,b)=1,Rightarrow, (10c!+!d,10a!+!b) = (ad!-!bc,10a!+!b), $ exactly as you observed.
Remark $ $ Various well-known divisibity test rules are essentially special cases of this, e.g. the rule for divisibility by $7$ follows from the rule for $21$ given below (we negated $,ad! -! bc = 2d!-!c,$ below)
$qquadqquad qquad , (10c!+!d,10(2)!+!1) = (c!-!2d, 10(2)!+!1)$
${rm similar to your} (10c!+!d,10(3)!+!1) = (c!-!3d, 10(3)!+!1) $ rule for $,31$
$endgroup$
It's the special case $m = 10c!+!d, n = 10a!+!b $ of the following
$quad bbox[5px,border:1px solid red]{(a,n) = 1,Rightarrow, (m,n) = (am!-!cn,n)} $ by $,(m,n)=(am,n) = (am!-!cn,n)$
So $ (a,b)=1,Rightarrow, (10c!+!d,10a!+!b) = (ad!-!bc,10a!+!b), $ exactly as you observed.
Remark $ $ Various well-known divisibity test rules are essentially special cases of this, e.g. the rule for divisibility by $7$ follows from the rule for $21$ given below (we negated $,ad! -! bc = 2d!-!c,$ below)
$qquadqquad qquad , (10c!+!d,10(2)!+!1) = (c!-!2d, 10(2)!+!1)$
${rm similar to your} (10c!+!d,10(3)!+!1) = (c!-!3d, 10(3)!+!1) $ rule for $,31$
edited Jan 6 at 21:54
answered Jan 6 at 20:43
Bill DubuqueBill Dubuque
209k29191633
209k29191633
$begingroup$
Do you know if there is a name for it? Or how I might find other work on it? I've used it to do some cool things with Gaussian integers and I highly doubt I'm the first person to play with this idea!
$endgroup$
– Ben Crossley
Jan 7 at 23:28
$begingroup$
@Ben I'm not aware of any common name for this. Things like this are folklore, e.g. occurring in various guises in divisibility tests. In number rings analogous results are often special cases of Hermite normal form algorithms for modules and related results, e.g. see here and here. If you give more details about your Gaussian integer results then I may be able to be more specific.
$endgroup$
– Bill Dubuque
Jan 8 at 0:45
$begingroup$
@Ben By the way, another angle is to view $,m = f(10),$ as a polynomial of degree $k$ in the radix. Then $$bmod 10a!+!b!:, 10equiv -b/a,Rightarrow,(f(10),10a!+!b) = (a^kf(-b/a),10a!+!b)qquad$$ and the algorithm can be viwed as a recursive scheme for evaluating $,a^kf(-b/a),$ (a homogeneous polynomial in $,a,b),,$ analogous to Horner evaluation and related results. If this is of interest let me know and I can elaborate.
$endgroup$
– Bill Dubuque
Jan 8 at 0:46
add a comment |
$begingroup$
Do you know if there is a name for it? Or how I might find other work on it? I've used it to do some cool things with Gaussian integers and I highly doubt I'm the first person to play with this idea!
$endgroup$
– Ben Crossley
Jan 7 at 23:28
$begingroup$
@Ben I'm not aware of any common name for this. Things like this are folklore, e.g. occurring in various guises in divisibility tests. In number rings analogous results are often special cases of Hermite normal form algorithms for modules and related results, e.g. see here and here. If you give more details about your Gaussian integer results then I may be able to be more specific.
$endgroup$
– Bill Dubuque
Jan 8 at 0:45
$begingroup$
@Ben By the way, another angle is to view $,m = f(10),$ as a polynomial of degree $k$ in the radix. Then $$bmod 10a!+!b!:, 10equiv -b/a,Rightarrow,(f(10),10a!+!b) = (a^kf(-b/a),10a!+!b)qquad$$ and the algorithm can be viwed as a recursive scheme for evaluating $,a^kf(-b/a),$ (a homogeneous polynomial in $,a,b),,$ analogous to Horner evaluation and related results. If this is of interest let me know and I can elaborate.
$endgroup$
– Bill Dubuque
Jan 8 at 0:46
$begingroup$
Do you know if there is a name for it? Or how I might find other work on it? I've used it to do some cool things with Gaussian integers and I highly doubt I'm the first person to play with this idea!
$endgroup$
– Ben Crossley
Jan 7 at 23:28
$begingroup$
Do you know if there is a name for it? Or how I might find other work on it? I've used it to do some cool things with Gaussian integers and I highly doubt I'm the first person to play with this idea!
$endgroup$
– Ben Crossley
Jan 7 at 23:28
$begingroup$
@Ben I'm not aware of any common name for this. Things like this are folklore, e.g. occurring in various guises in divisibility tests. In number rings analogous results are often special cases of Hermite normal form algorithms for modules and related results, e.g. see here and here. If you give more details about your Gaussian integer results then I may be able to be more specific.
$endgroup$
– Bill Dubuque
Jan 8 at 0:45
$begingroup$
@Ben I'm not aware of any common name for this. Things like this are folklore, e.g. occurring in various guises in divisibility tests. In number rings analogous results are often special cases of Hermite normal form algorithms for modules and related results, e.g. see here and here. If you give more details about your Gaussian integer results then I may be able to be more specific.
$endgroup$
– Bill Dubuque
Jan 8 at 0:45
$begingroup$
@Ben By the way, another angle is to view $,m = f(10),$ as a polynomial of degree $k$ in the radix. Then $$bmod 10a!+!b!:, 10equiv -b/a,Rightarrow,(f(10),10a!+!b) = (a^kf(-b/a),10a!+!b)qquad$$ and the algorithm can be viwed as a recursive scheme for evaluating $,a^kf(-b/a),$ (a homogeneous polynomial in $,a,b),,$ analogous to Horner evaluation and related results. If this is of interest let me know and I can elaborate.
$endgroup$
– Bill Dubuque
Jan 8 at 0:46
$begingroup$
@Ben By the way, another angle is to view $,m = f(10),$ as a polynomial of degree $k$ in the radix. Then $$bmod 10a!+!b!:, 10equiv -b/a,Rightarrow,(f(10),10a!+!b) = (a^kf(-b/a),10a!+!b)qquad$$ and the algorithm can be viwed as a recursive scheme for evaluating $,a^kf(-b/a),$ (a homogeneous polynomial in $,a,b),,$ analogous to Horner evaluation and related results. If this is of interest let me know and I can elaborate.
$endgroup$
– Bill Dubuque
Jan 8 at 0:46
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064058%2fname-for-this-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown